Standard

Complexity of aperiodicity for topological properties of regular ω-languages. / Selivanov, Victor L.; Wagner, Klaus W.

Logic and Theory of Algorithms (CiE 2008). 2008. p. 533-543 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5028).

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

Harvard

Selivanov, VL & Wagner, KW 2008, Complexity of aperiodicity for topological properties of regular ω-languages. in Logic and Theory of Algorithms (CiE 2008). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5028, pp. 533-543, Computability in europe-2008, 15/06/08. https://doi.org/10.1007/978-3-540-69407-6_57

APA

Selivanov, V. L., & Wagner, K. W. (2008). Complexity of aperiodicity for topological properties of regular ω-languages. In Logic and Theory of Algorithms (CiE 2008) (pp. 533-543). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5028). https://doi.org/10.1007/978-3-540-69407-6_57

Vancouver

Selivanov VL, Wagner KW. Complexity of aperiodicity for topological properties of regular ω-languages. In Logic and Theory of Algorithms (CiE 2008). 2008. p. 533-543. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-69407-6_57

Author

Selivanov, Victor L. ; Wagner, Klaus W. / Complexity of aperiodicity for topological properties of regular ω-languages. Logic and Theory of Algorithms (CiE 2008). 2008. pp. 533-543 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{c1a80eb3239b4478885153390d64274c,
title = "Complexity of aperiodicity for topological properties of regular ω-languages",
abstract = "We study the complexity of aperiodicity restricted to topological properties of regular ω-languages (i.e. properties closed under the Wadge equivalence on the Cantor space of ω-words) restricted to aperiodic sets. In particular, we show the -completeness of such problems for several usual deterministic and non-deterministic automata representations of regular ω-languages. {\textcopyright} 2008 Springer-Verlag Berlin Heidelberg.",
keywords = "Aperiodic automaton, Deterministic Muller automaton, Monadic second-order formula, Nondeterministic B{\"u}chi automaton, Regular aperiodic ω-language, Wadge reducibility",
author = "Selivanov, {Victor L.} and Wagner, {Klaus W.}",
year = "2008",
month = jul,
day = "1",
doi = "10.1007/978-3-540-69407-6_57",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "533--543",
booktitle = "Logic and Theory of Algorithms (CiE 2008)",
note = "Computability in europe-2008 ; Conference date: 15-06-2008",

}

RIS

TY - GEN

T1 - Complexity of aperiodicity for topological properties of regular ω-languages

AU - Selivanov, Victor L.

AU - Wagner, Klaus W.

PY - 2008/7/1

Y1 - 2008/7/1

N2 - We study the complexity of aperiodicity restricted to topological properties of regular ω-languages (i.e. properties closed under the Wadge equivalence on the Cantor space of ω-words) restricted to aperiodic sets. In particular, we show the -completeness of such problems for several usual deterministic and non-deterministic automata representations of regular ω-languages. © 2008 Springer-Verlag Berlin Heidelberg.

AB - We study the complexity of aperiodicity restricted to topological properties of regular ω-languages (i.e. properties closed under the Wadge equivalence on the Cantor space of ω-words) restricted to aperiodic sets. In particular, we show the -completeness of such problems for several usual deterministic and non-deterministic automata representations of regular ω-languages. © 2008 Springer-Verlag Berlin Heidelberg.

KW - Aperiodic automaton

KW - Deterministic Muller automaton

KW - Monadic second-order formula

KW - Nondeterministic Büchi automaton

KW - Regular aperiodic ω-language

KW - Wadge reducibility

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

U2 - 10.1007/978-3-540-69407-6_57

DO - 10.1007/978-3-540-69407-6_57

M3 - Conference contribution

AN - SCOPUS:45849085784

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

SP - 533

EP - 543

BT - Logic and Theory of Algorithms (CiE 2008)

T2 - Computability in europe-2008

Y2 - 15 June 2008

ER -

ID: 127088014