A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Language Equations with Symmetric Difference
Tekijät: Okhotin A
Kustantaja: IOS PRESS
Julkaisuvuosi: 2012
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Numero sarjassa: 41730
Vuosikerta: 116
Numero: 41730
Aloitussivu: 205
Lopetussivu: 222
Sivujen määrä: 18
ISSN: 0169-2968
DOI: https://doi.org/10.3233/FI-2012-679
Tiivistelmä
The paper investigates the expressive power of language equations with the operations of concatenation and symmetric difference. For equations over every finite alphabet Sigma with vertical bar Sigma vertical bar >= 1, it is demonstrated that the sets representable by unique solutions of such equations are exactly the recursive sets over Sigma, and the sets representable by their least (greatest) solutions are exactly the recursively enumerable sets (their complements, respectively). If vertical bar Sigma vertical bar >= 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 Pi(0)(1)-complete, the existence of a unique, a least or a greatest solution is Pi(0)(2)-complete, while the existence of finitely many solutions is Sigma(0)(3)-complete.
The paper investigates the expressive power of language equations with the operations of concatenation and symmetric difference. For equations over every finite alphabet Sigma with vertical bar Sigma vertical bar >= 1, it is demonstrated that the sets representable by unique solutions of such equations are exactly the recursive sets over Sigma, and the sets representable by their least (greatest) solutions are exactly the recursively enumerable sets (their complements, respectively). If vertical bar Sigma vertical bar >= 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 Pi(0)(1)-complete, the existence of a unique, a least or a greatest solution is Pi(0)(2)-complete, while the existence of finitely many solutions is Sigma(0)(3)-complete.
Turun yliopiston Tutkimustietojärjestelmän portaali