Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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 |
Опубликовано для внешнего пользования | Да |
ID: 41141424