Complexity of aperiodicity for topological properties of regular ω-languages

DOI

https://doi.org/10.1007/978-3-540-69407-6_57
Final published version

Victor L. Selivanov
Klaus W. Wagner

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.

Original language	English
Title of host publication	Logic and Theory of Algorithms (CiE 2008)
Pages	533-543
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-540-69407-6_57
State	Published - 1 Jul 2008
Event	Computability in europe-2008 - Duration: 15 Jun 2008 → …

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Nature
Volume	5028
ISSN (Print)	0302-9743

Conference

Conference	Computability in europe-2008
Period	15/06/08 → …

Research areas

Aperiodic automaton, Deterministic Muller automaton, Monadic second-order formula, Nondeterministic Büchi automaton, Regular aperiodic ω-language, Wadge reducibility

ID: 127088014