• Alexander Okhotin

Systems of language equations of the form {φ(X1, . . . , Xn) = ∅, ψ(X1, . . . , Xn) ≠ ∅} are studied, where φ, ψ may contain set-theoretic operations and concatenation; they can be equivalently represented as strict inequalities ξ(X1, . . . , Xn) ⊂ L0. It is proved that the problem whether such an inequality has a solution is Σ2-complete, the problem whether it has a unique solution is in (Σ3 ∩ ∏3)\ (Σ2 ∪ ∏2), the existence of a regular solution is a Σ1-complete problem, while testing whether there are finitely many solutions is Σ3-complete. The class of languages representable by their unique solutions is exactly the class of recursive sets, though a decision procedure cannot be algorithmically constructed out of an inequality, even if a proof of solution uniqueness is attached.

Язык оригиналаанглийский
Название основной публикацииMFCS 2005: Mathematical Foundations of Computer Science 2005
Страницы708-719
Число страниц12
Том3618
СостояниеОпубликовано - 24 окт 2005
Опубликовано для внешнего пользованияДа
Событие30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Польша
Продолжительность: 29 авг 20052 сен 2005

Серия публикаций

НазваниеLecture Notes in Computer Science
ИздательSpringer
ISSN (печатное издание)0302-9743

конференция

конференция30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005
Страна/TерриторияПольша
ГородGdansk
Период29/08/052/09/05

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

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

ID: 41141085