MIX is a 2-MCFL and the word problem in Z2 Z 2 is captured by the IO and the OI hierarchies
In this work we establish that the language MIX={w?{a;b;c}?||w|a=|w|b=|w|c} MIX = { w ? { a ; b ; c } ? | | w | a = | w | b = | w | c } and the language O 2 = { w ? { a ; a  ; b ; b  } | | w | a = | w | a  ? | w | b = | w | b  } are 2-MCFLs. As 2-MCFLs form a class of languages that is included in both the IO and OI hierarchies, and as O2 O 2 is the group language of a simple presentation of Z2 Z 2 we exhibit here the first, to our knowledge, non-virtually-free group language (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.
io and oi hierarchies group languages mildly context sensitive languages formal language theory higher-order collapsible pushdown automata algebraic topology jordan curves