Titre :

On is an n-MCFL

Auteur(s) :

Gebhardt, Kilian [Auteur]
Hochschule für Technik und Wirtschaft [Dresden] [HTW Dresden ]
Meunier, Frédéric [Auteur]
Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique [CERMICS]
École nationale des ponts et chaussées [ENPC]
Salvati, Sylvain [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]
Université de Lille

Titre de la revue :

Journal of Computer and System Sciences

Pagination :

41-52

Éditeur :

Elsevier

Date de publication :

2022-08-01

ISSN :

0022-0000

Discipline(s) HAL :

Informatique [cs]/Informatique et langage [cs.CL]
Mathématiques [math]/Topologie algébrique [math.AT]
Mathématiques [math]/Combinatoire [math.CO]
Mathématiques [math]/Théorie des groupes [math.GR]

Résumé en anglais : [en]

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$, ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL