@TechReport{      salvati:inria-00564552,
  Author        = "Salvati, Sylvain",
  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.}",
  affiliation   = "SIGNES - INRIA Bordeaux - Sud-Ouest",
  date-added    = "2013-12-14 15:45:48 +0000",
  date-modified = "2013-12-14 15:45:48 +0000",
  hal_id        = "inria-00564552",
  Language      = "Anglais",
  Month         = "February",
  PDF           = "http://hal.inria.fr/inria-00564552/PDF/mix.pdf",
  Title         = "{MIX is a 2-MCFL and the word problem in $\mathbb{Z}^2$ is solved by a third-order collapsible pushdown automaton}",
  Type          = "Rapport de recherche",
  URL           = "http://hal.inria.fr/inria-00564552",
  Year          = "2011",
  bdsk-url-1    = "http://hal.inria.fr/inria-00564552",
  File          = "MIX is a 2-MCFL and the word problem in $Z^2$ is solved by a third-order collapsible pushdown automaton - Salvati (0) (0) - a - a - r.pdf"
}

@TechReport{ salvati:inria-00564552, Author = "Salvati, Sylvain", 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|\ \land |w|\}b = |w|\", affiliation = "SIGNES - INRIA Bordeaux - Sud-Ouest", date-added = "2013-12-14 15:45:48 +0000", date-modified = "2013-12-14 15:45:48 +0000", hal_id = "inria-00564552", Language = "Anglais", Month = "February", PDF = "http://hal.inria.fr/inria-00564552/PDF/mix.pdf", Title = "{MIX is a 2-MCFL and the word problem in $\mathbb{Z}^2$ is solved by a third-order collapsible pushdown automaton}", Type = "Rapport de recherche", URL = "http://hal.inria.fr/inria-00564552", Year = "2011", bdsk-url-1 = "http://hal.inria.fr/inria-00564552", File = "MIX is a 2-MCFL and the word problem in $Z^2$ is solved by a third-order collapsible pushdown automaton - Salvati (0) (0) - a - a - r.pdf" }}}}$ 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.