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 languageEnglish
Pages (from-to)112-126
Number of pages15
JournalTheoretical Computer Science
Volume376
Issue number1-2
DOIs
StatePublished - 10 May 2007
Externally publishedYes

    Research areas

  • Complementation, Computational complexity, Decision problems, Language equations, Negation

    Scopus subject areas

  • Computational Theory and Mathematics

ID: 41141424