The paper studies resolved systems of language equations that allow the use of all Boolean operations in addition to concatenation. Existence and uniqueness of solutions are shown to be their nontrivial properties, these properties are given characterizations by first order formulae, and the position of the corresponding decision problems in the arithmetical hierarchy is determined. The class of languages defined by components of unique solutions of such systems is shown to coincide with the class of recursive languages.
| Original language | English |
|---|---|
| Title of host publication | ICALP 2003: Automata, Languages and Programming |
| Pages | 239-251 |
| Number of pages | 13 |
| Volume | 2719 |
| State | Published - 1 Dec 2003 |
| Externally published | Yes |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Publisher | Springer |
| ISSN (Print) | 0302-9743 |
ID: 41144716