TY - CHAP

T1 - Decision problems for language equations with Boolean operations

AU - Okhotin, Alexander

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

KW - Boolean operations

KW - Language equations

KW - Recursive sets

UR - http://www.scopus.com/inward/record.url?scp=35248835505&partnerID=8YFLogxK

M3 - Chapter

AN - SCOPUS:35248835505

VL - 2719

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 239

EP - 251

BT - ICALP 2003: Automata, Languages and Programming

ER -