Complexity of Aperiodicity for Topological Properties of Regular ω-Languages

DOI10.1007/978-3-540-69407-6_57zbMath1143.68039OpenAlexW1550718696MaRDI QIDQ3507470

Klaus W. Wagner, Victor L. Selivanov

Publication date: 19 June 2008

Published in: Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69407-6_57

zbMATH Keywords

Wadge reducibilitydeterministic Muller automatonmonadic second-order formulaaperiodic automatonnondeterministic Büchi automatonregular aperiodic \(\omega \)-language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Descriptive set theory (03E15) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

On the main scientific achievements of Victor Selivanov ⋮ Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: Complexity of Aperiodicity for Topological Properties of Regular ω-Languages