28973 articles – 22398 references  [version française]

inria-00564552, version 1

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

(2011)

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.

  • 1:  SIGNES (INRIA Bordeaux - Sud-Ouest)
  • INRIA – CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – Université Michel de Montaigne - Bordeaux III – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
  • Domain : Mathematics/Group Theory
    Mathematics/Algebraic Topology
    Computer Science/Formal Languages and Automata Theory
    Computer Science/Computation and Language
 
  • inria-00564552, version 1
  • oai:hal.inria.fr:inria-00564552
  • From: 
  • Submitted on: Wednesday, 9 February 2011 11:14:58
  • Updated on: Wednesday, 9 February 2011 11:42:38