MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies (Q2353402)

Different presentations of the same group define different group languages that can be translated into each other by rational transductions. A general question consists in relating algebraic properties of finitely presented and finitely generated groups with language-theoretic properties of their group languages. Such a question can be partially answered by characterizing the groups whose group-languages belong to a certain class of languages that is closed under rational transduction. The groups whose group languages are regular languages are finite groups and those whose group languages are context-free languages are virtually free groups [\textit{D. E. Muller} and \textit{P. E. Schupp}, J. Comput. Syst. Sci. 26, 295--310 (1983; Zbl 0537.20011)]. The group language of a simple presentation of \(\mathbb{Z}^2\) is the 2-dimensional origin-crossing language \(O_2=\{w \in \{a,\bar{a},b,\bar{b}\}^* \mid | w|_{a}=| w|_{\bar{a}}\land | w|_{b}=| w|_{\bar{b}}\}\), which is not context-free. An open problem in computational group theory is whether \(O_2\) is an indexed language. In this paper, the author shows that the problems whether MIX \(=\{w \in \{a,b,c\}^* \mid | w|_{a}= | w|_{b}=| w|_{c}\}\) and \(O_2\) are indexed languages are in fact equivalent, and he proves that MIX and \(O_2\) are 2-multiple context-free languages (MCFL). 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\), this gives a non-virtually-free group language (i.e. non-context-free group language) that is captured by the IO and OI hierarchies. Furthermore, the author proves MIX is not a mildly context-sensitive language.