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

1 PoSET - Models for a Structured Programming of Space and Time
LaBRI - Laboratoire Bordelais de Recherche en Informatique, SCRIME - Studio de Création et de Recherche en Informatique et Musique Électroacoustique, Inria Bordeaux - Sud-Ouest
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.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2015, 81 (7), pp.1252 - 1277. 〈http://www.sciencedirect.com/science/article/pii/S0022000015000264〉
Domaine :

Littérature citée [33 références]

https://hal.inria.fr/inria-00564552
Contributeur : Sylvain Salvati <>
Soumis le : mercredi 9 février 2011 - 11:14:58
Dernière modification le : jeudi 11 janvier 2018 - 06:27:22
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〉

### Métriques

Consultations de la notice

## 445

Téléchargements de fichiers