Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429983 | Journal of Computer and System Sciences | 2015 | 26 Pages |
Abstract
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 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 O2O2 is the group language of a simple presentation of Z2Z2 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sylvain Salvati,