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

Sylvain Salvati 1, 2
1 PoSET - Models for a Structured Programming of Space and Time
Inria Bordeaux - Sud-Ouest, SCRIME - Studio de Création et de Recherche en Informatique et Musique Électroacoustique, LaBRI - Laboratoire Bordelais de Recherche en Informatique
Abstract : 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.
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00564552
Contributeur : Sylvain Salvati <>
Soumis le : mercredi 9 février 2011 - 11:14:58
Dernière modification le : mardi 29 mai 2018 - 09:14:04
Document(s) archivé(s) le : samedi 3 décembre 2016 - 19:06:41

Fichier

mix.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00564552, version 1

Citation

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, Elsevier, 2015, 81 (7), pp.1252 - 1277. 〈http://www.sciencedirect.com/science/article/pii/S0022000015000264〉. 〈inria-00564552〉

Partager

Métriques

Consultations de la notice

489

Téléchargements de fichiers

470