O_n is an n-MCFL

2020/12/22 by Kilian Gebhardt, Gebhardt, Kilian, Frédéric Meunier +3 · 1 citation
Computer Science · Social Sciences · #20K15 #68Q45 #Constraint Satisfaction and Optimization #Digital Filter Design and Implementation #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Multimedia Communication and Technology

paper · pdf · doi:10.48550/arxiv.2012.12100

openalex publication_date 2020/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language O_n, the language that contains the same number of letters a_i and a_i with 1≤ i≤ n, in the known classes of formal languages. It has recently been shown that O_n is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that O_n is an MCFL of dimension n was left open. We present two proofs of this conjecture, both relying on tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.

Cited by

• A substitution lemma for multiple context-free languages

Related

• A Topological proof that O₂ is 2-MCFL
• O₂ is a multiple context-free grammar: an implementation-, formalisation-friendly proof
• A short proof that O₂ is an MCFL
• The Word Problem of ℤⁿ Is a Multiple Context-Free Language
• Permutation closure for multiple context-free languages