On is an n-MCFL
Autor: | Kilian Gebhardt, Frédéric Meunier, Sylvain Salvati |
---|---|
Přispěvatelé: | 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), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-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), 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) |
Jazyk: | angličtina |
Rok vydání: | 2022 |
Předmět: |
Computational Theory and Mathematics
General Computer Science Computer Networks and Communications Applied Mathematics [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] Theoretical Computer Science |
Zdroj: | Journal of Computer and System Sciences Journal of Computer and System Sciences, 2022, 127, pp.41-52. ⟨10.1016/j.jcss.2022.02.003⟩ |
ISSN: | 0022-0000 1090-2724 |
DOI: | 10.1016/j.jcss.2022.02.003⟩ |
Popis: | International audience; 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. |
Databáze: | OpenAIRE |
Externí odkaz: |