Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
Язык оригинала | английский |
---|---|
Название основной публикации | Developments in Language Theory - 10th International Conference, DLT 2006, Proceedings |
Издатель | Springer Nature |
Страницы | 420-432 |
Число страниц | 13 |
ISBN (печатное издание) | 354035428X, 9783540354284 |
DOI | |
Состояние | Опубликовано - 1 янв 2006 |
Опубликовано для внешнего пользования | Да |
Событие | 10th International Conference on Developments in Language Theory, DLT 2006 - Santa Barbara, CA, Соединенные Штаты Америки Продолжительность: 26 июн 2006 → 29 июн 2006 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 4036 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 10th International Conference on Developments in Language Theory, DLT 2006 |
---|---|
Страна/Tерритория | Соединенные Штаты Америки |
Город | Santa Barbara, CA |
Период | 26/06/06 → 29/06/06 |
ID: 41144089