MIX is a 2-MCFL and the word problem in $\mathbb{Z}^2$ is solved by a third-order collapsible pushdown automaton - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Computer and System Sciences Année : 2015

MIX is a 2-MCFL and the word problem in $\mathbb{Z}^2$ is solved by a third-order collapsible pushdown automaton

Résumé

In this work we establish that the language $MIX = \{w \in \{a;b;c\}^\ast \vert |w|_a = |w|_b = |w|_c\}$ and the language $O_2 = \{w \in \{a;\overline{a};b;\overline{b}\} \vert |w|_a = |w|_{\overline{a}} \land |w|_b = |w|_{\overline{b}}\}$ are 2-MCFLs. As 2-MCFLs form a class of languages that is included in both the IO and OI hierarchies, and as $O_2$ is the group language of a simple presentation of $\mathbb{Z}^2$ we exhibit here the first, to our knowledge, non-virtually-free group language (\textit{i.e.} non-context-free group language) that is captured by the IO and OI hierarchies. Moreover, it was a long-standing open problem whether MIX was a mildly context sensitive language or not, and it was conjectured that it was not, so we close this conjecture by giving it a negative answer.
Fichier principal
Vignette du fichier
mix.pdf (466.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00564552 , version 1 (09-02-2011)

Identifiants

  • HAL Id : inria-00564552 , version 1

Citer

Sylvain Salvati. MIX is a 2-MCFL and the word problem in $\mathbb{Z}^2$ is solved by a third-order collapsible pushdown automaton. Journal of Computer and System Sciences, 2015, 81 (7), pp.1252 - 1277. ⟨inria-00564552⟩

Collections

CNRS INRIA INRIA2
321 Consultations
440 Téléchargements

Partager

Gmail Facebook X LinkedIn More