Complementing deterministic Büchi automata in polynomial time

DOI10.1016/0022-0000(87)90036-5zbMath0666.68058OpenAlexW1994797527MaRDI QIDQ1116702

Robert Kurshan

Publication date: 1987

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(87)90036-5

zbMATH Keywords

time complexityformal languageBüchi automaton\(\omega\)-language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Automata Theory and Model Checking ⋮ Multi-Valued Reasoning about Reactive Systems ⋮ A transformation-based approach to implication of GSTE assertion graphs ⋮ On the power of finite ambiguity in Büchi complementation ⋮ Mechanizing the Powerset Construction for Restricted Classes of ω-Automata ⋮ Unnamed Item ⋮ A complete characterization of deterministic regular liveness properties ⋮ A unified approach for showing language inclusion and equivalence between various types of \(\omega\)-automata ⋮ Tool support for learning Büchi automata and linear temporal logic ⋮ Relating word and tree automata ⋮ A theory of timed automata

Cites Work

• Theories of automata on \(\omega\)-tapes: a simplified approach
• The monadic second order theory of all countable ordinals
• Büchi's monadic second order successor arithmetic.
• Synthesis of Communicating Processes from Temporal Logic Specifications
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item