1. On is an n-MCFL
- Author
-
Gebhardt, Kilian, Meunier, Frédéric, Salvati, Sylvain, Hochschule für Technik und Wirtschaft [Dresden] (HTW Dresden ), École des Ponts ParisTech (ENPC), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), Université de Lille, Linking Dynamic Data (LINKS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), and Université de Lille, INRIA, CRIStAL CNRS
- Subjects
[MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT] ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] ,[MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR] - 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 $\bar a_i$ with $1\leq i\leq 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.
- Published
- 2018