Standard

Decision problems for language equations with Boolean operations. / Okhotin, Alexander.

ICALP 2003: Automata, Languages and Programming. Vol. 2719 2003. p. 239-251 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

Harvard

Okhotin, A 2003, Decision problems for language equations with Boolean operations. in ICALP 2003: Automata, Languages and Programming. vol. 2719, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 239-251.

APA

Okhotin, A. (2003). Decision problems for language equations with Boolean operations. In ICALP 2003: Automata, Languages and Programming (Vol. 2719, pp. 239-251). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Vancouver

Okhotin A. Decision problems for language equations with Boolean operations. In ICALP 2003: Automata, Languages and Programming. Vol. 2719. 2003. p. 239-251. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Author

Okhotin, Alexander. / Decision problems for language equations with Boolean operations. ICALP 2003: Automata, Languages and Programming. Vol. 2719 2003. pp. 239-251 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inbook{35334f1b5cd94e6b827a061b7355a914,
title = "Decision problems for language equations with Boolean operations",
abstract = "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.",
keywords = "Boolean operations, Language equations, Recursive sets",
author = "Alexander Okhotin",
year = "2003",
month = dec,
day = "1",
language = "English",
volume = "2719",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "239--251",
booktitle = "ICALP 2003: Automata, Languages and Programming",

}

RIS

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 -

ID: 41144716