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.

Original languageEnglish
Title of host publicationICALP 2003: Automata, Languages and Programming
Pages239-251
Number of pages13
Volume2719
StatePublished - 1 Dec 2003
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
ISSN (Print)0302-9743

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

    Research areas

  • Boolean operations, Language equations, Recursive sets

ID: 41144716