Systems of language equations of the form Xi = φi(X1,..., Xn) (1 ≤ t ≤ n) are studied, in which every φi may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is in co-RE and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. The position of the languages defined by these equations in the hierarchy of language families is established.
| Original language | English |
|---|---|
| Title of host publication | Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings |
| Publisher | Springer Nature |
| Pages | 420-432 |
| Number of pages | 13 |
| ISBN (Print) | 354035428X, 9783540354284 |
| DOIs | |
| State | Published - 1 Jan 2006 |
| Externally published | Yes |
| Event | 10th International Conference on Developments in Language Theory, DLT 2006 - Santa Barbara, CA, United States Duration: 26 Jun 2006 → 29 Jun 2006 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 4036 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 10th International Conference on Developments in Language Theory, DLT 2006 |
|---|---|
| Country/Territory | United States |
| City | Santa Barbara, CA |
| Period | 26/06/06 → 29/06/06 |
ID: 41144089