MIX is a 2-MCFL and the word problem in Z2 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} and the language O2={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 is the group language of a simple presentation of Z2 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.