TY - JOUR

T1 - Language equations with symmetric difference

AU - Okhotin, Alexander

PY - 2012/5/28

Y1 - 2012/5/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84861371734&partnerID=8YFLogxK

U2 - 10.3233/FI-2012-679

DO - 10.3233/FI-2012-679

M3 - Article

AN - SCOPUS:84861371734

VL - 116

SP - 205

EP - 222

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-4

ER -