Complexity of Topological Properties of Regular ω-Languages

DOI10.1007/978-3-540-85780-8_42zbMath1159.68019OpenAlexW1708543839MaRDI QIDQ3533038

Victor L. Selivanov, Klaus W. Wagner

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_42

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (1)

On the main scientific achievements of Victor Selivanov

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complementation problem for Büchi automata with applications to temporal logic
• Fine hierarchy of regular \(\omega\)-languages
• Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
• On ω-regular sets
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• Chains and Superchains for ω-Rational Sets, Automata and Semigroups
• Structural complexity of ω-automata
• Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time
• THE MISSING LINK FOR ω-RATIONAL SETS, AUTOMATA, AND SEMIGROUPS
• Decision problems forω-automata

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