Systems of language equations of the form Xi = φi (X1, ..., Xn) (1 ≤ i ≤ n) are studied. Here 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 PSPACE-hard and is in co-RE, and its decidability remains, in general, open. Uniqueness becomes decidable in the case of a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete.
| Original language | English |
|---|---|
| Pages (from-to) | 112-126 |
| Number of pages | 15 |
| Journal | Theoretical Computer Science |
| Volume | 376 |
| Issue number | 1-2 |
| DOIs | |
| State | Published - 10 May 2007 |
| Externally published | Yes |
ID: 41141424