Decision problems for language equations with Boolean operations

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийглава/разделнаучнаярецензирование

26 Цитирования (Scopus)

Аннотация

The paper studies resolved systems of language equations that allow the use of all Boolean operations in addition to concatenation. Existence and uniqueness of solutions are shown to be their nontrivial properties, these properties are given characterizations by first order formulae, and the position of the corresponding decision problems in the arithmetical hierarchy is determined. The class of languages defined by components of unique solutions of such systems is shown to coincide with the class of recursive languages.

Язык оригиналаанглийский
Название основной публикацииICALP 2003: Automata, Languages and Programming
Страницы239-251
Число страниц13
Том2719
СостояниеОпубликовано - 1 дек 2003
Опубликовано для внешнего пользованияДа

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

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

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

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

Fingerprint

Подробные сведения о темах исследования «Decision problems for language equations with Boolean operations». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать