Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata

DOI10.1007/978-3-642-00596-1_14zbMath1234.68221OpenAlexW1515863024MaRDI QIDQ3617729

Orna Kupferman, Nir Piterman

Publication date: 31 March 2009

Published in: Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00596-1_14

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Alternating finite automata on \(\omega\)-words
• Reasoning about infinite computations
• Weak alternating automata are not that weak
• Alternation
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Finding Shortest Witnesses to the Nonemptiness of Automata on Infinite Words
• Safraless Compositional Synthesis