BÜCHI COMPLEMENTATION MADE TIGHTER

DOI10.1142/S0129054106004145zbMath1096.68081OpenAlexW4246764629MaRDI QIDQ5484906

Orna Kupferman, Ehud Friedgut, Moshe Y. Vardi

Publication date: 21 August 2006

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054106004145

zbMATH Keywords

complementationnondeterministic Büchi automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

Automata Theory and Model Checking ⋮ Multi-Valued Reasoning about Reactive Systems ⋮ On the power of finite ambiguity in Büchi complementation ⋮ Towards a grand unification of Büchi complementation constructions ⋮ Profile trees for Büchi word automata, with application to determinization ⋮ Automata-Theoretic Model Checking Revisited ⋮ Tighter Bounds for the Determinisation of Büchi Automata ⋮ State of Büchi Complementation ⋮ \( \omega \)-automata

Cites Work

• Unnamed Item
• Partial orders on words, minimal elements of regular languages, and state complexity
• The complementation problem for Büchi automata with applications to temporal logic
• Alternating automata on infinite trees
• Reasoning about infinite computations
• Fair simulation
• Asymptotic Estimates of Stirling Numbers
• Temporal logic can be more expressive
• Weak alternating automata are not that weak

This page was built for publication: BÜCHI COMPLEMENTATION MADE TIGHTER