Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time

DOI10.1007/3-540-59293-8_202zbMath1496.68183OpenAlexW1557288551MaRDI QIDQ5096738

Thomas Wilke, Haiseung Yoo

Publication date: 18 August 2022

Published in: TAPSOFT '95: Theory and Practice of Software Development (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59293-8_202

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)

Related Items (9)

On omega context free languages which are Borel sets of infinite rank. ⋮ Fine hierarchy of regular \(\omega\)-languages ⋮ Ambiguity in omega context free languages ⋮ Unnamed Item ⋮ Complexity of Topological Properties of Regular ω-Languages ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ Wadge-Wagner hierarchies

Cites Work

• Fine hierarchy of regular \(\omega\)-languages
• On ω-regular sets
• Structural complexity of ω-automata
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time