DOI

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.

Язык оригиналаанглийский
Страницы (с-по)112-126
Число страниц15
ЖурналTheoretical Computer Science
Том376
Номер выпуска1-2
DOI
СостояниеОпубликовано - 10 мая 2007
Опубликовано для внешнего пользованияДа

    Предметные области Scopus

  • Математика и теория расчета

ID: 41141424