Language equations with symmetric difference (Q2893311)

The paper investigates the expressive power of explicit systems of language equations with the operations of concatenation and symmetric difference, and with regular constants (it can be easily seen that for such equations, explicit systems are as powerful as implicit ones). The main result asserts that these systems have the same expressive power as those with all Boolean operations, that is, components of their unique solutions are exactly recursive sets, while components of their least and greatest solutions are exactly recursively enumerable sets and their complements, respectively. For one-letter alphabets, this result is obtained directly from the universality result for implicit systems of language equations over a one-letter alphabet with concatenation as the only operation, due to \textit{A.~Jeż} and the author [LIPICS -- Leibniz International Proceedings in Informatics 3, 577--588 (2009; Zbl 1236.68171)]. For alphabets with at least two letters, it is proved that symmetric difference and linear concatenation are sufficient to achieve universality. The proof proceeds by expressing intersection of languages of a special form using these two operations, and then constructing a suitable encoding of computations of a Turing machine as an intersection of two unambiguous linear context-free languages of the required form. As a consequence of the main theorem, it is proved that basic decision problems for these systems of equations are complete for the same levels of the arithmetical hierarchy as in the case of systems with all Boolean operations.