|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 7 van 22 gevonden artikelen
| Titel: |
Language Equations with Symmetric Difference |
| Auteur: |
Okhotin, Alexander |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 116 (2012) nr. 1-4 pagina's 205-222 |
| Jaar: |
2012-05-16 |
| Inhoud: |
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 Π01-complete, the existence of a unique, a least or a greatest solution is Π02-complete, while the existence of finitely many solutions is Π03-complete. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 7 van 22 gevonden artikelen
| << vorige | volgende >> |