Comparing consecutive letter counts in multiple context-free languages

2020/02/19 by Lehner, Florian, Lindorfer, Christian · 1 citation
#68Q45 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2002.08236

Abstract

Context-free grammars are not able to model cross-serial dependencies in natural languages. To overcome this issue, Seki et al. introduced a generalization called m-multiple context-free grammars (m-MCFGs), which deal with m-tuples of strings. We show that m-MCFGs are capable of comparing the number of consecutive occurrences of at most 2m different letters. In particular, the language \a₁^n₁ a₂^n₂ … a_k^n_2m+1 | n₁ ≥ n₂ ≥ … ≥ n_2m+1 ≥ 0\ is (m+1)-multiple context-free, but not m-multiple context-free.

Cited by

• A substitution lemma for multiple context-free languages

Related

• O₂ is a multiple context-free grammar: an implementation-, formalisation-friendly proof
• Multiple Context-Free Tree Grammars: Lexicalization and Characterization
• Counting on General Run-Length Grammars
• Permutation closure for multiple context-free languages
• Computing all-vs-all MEMs in grammar-compressed text