DOI

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 июн 200629 июн 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/0629/06/06

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

  • Компьютерные науки (все)
  • Теоретические компьютерные науки

ID: 41144089