Article Dans Une Revue
Journal of Computer and System Sciences
Année : 2015
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.
Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...
Sylvain Salvati : Connectez-vous pour contacter le contributeur
https://inria.hal.science/inria-00564552
Soumis le : mercredi 9 février 2011-11:14:58
Dernière modification le : vendredi 5 avril 2024-10:09:24
Archivage à long terme le : samedi 3 décembre 2016-19:06:41
Dates et versions
- 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⟩
330
Consultations
466
Téléchargements