Language Equations with Symmetric Difference

The paper investigates the expressive power of language equations with the operations of concatenation and symmetric difference. For equations over every finite alphabet Σ with |Σ| ≥1, it is demonstrated that the sets representable by unique solutions of such equations are exactly the recursive sets over , and the sets representable by their least (greatest) solutions are exactly the recursively enumerable sets (their complements, respectively). If |Σ| ≥ 2, the same characterization holds already for equations using symmetric difference and linear concatenation with regular constants. In both cases, the solution existence problem is Π (0,1)-complete, the existence of a unique, a least or a greatest solution is Π(0,2)-complete, while the existence of finitely many solutions is Σ(0,3)-complete.