Sky is not the limit. Tighter rank bounds for elevator automata in Büchi automata complementation

DOI10.1007/978-3-030-99527-0_7MaRDI QIDQ6535611zbMATH OpenFDO

Authors Vojtěch Havlena, Ondřej Lengál

Publication date 1 February 2024

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-030-99527-0_7

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Complementing Büchi Automata with Ranker
• Modular mix-and-match complementation of Büchi automata
• Unifying Büchi complementation constructions
• Simulations in rank-based Büchi automata complementation
• Improved Ramsey-based Büchi complementation

Cites work

• A simple and optimal complementation algorithm for Büchi automata
• Advanced automata minimization
• An improved construction of deterministic omega-automaton using derivatives
• BÜCHI COMPLEMENTATION MADE TIGHTER
• Büchi Complementation and Size-Change Termination
• Büchi complementation made tight
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• Complementing deterministic Büchi automata in polynomial time
• Complementing semi-deterministic Büchi automata
• Experimental Evaluation of Classical Automata Constructions
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• scientific article; zbMATH DE number 5872401 (Why is no real title available?)
• scientific article; zbMATH DE number 1324833 (Why is no real title available?)
• scientific article; zbMATH DE number 1765703 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Improved Ramsey-based Büchi complementation
• Learning to complement Büchi automata
• Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
• New optimizations and heuristics for determinization of Büchi automata
• On complementing nondeterministic Büchi automata
• On minimal odd rankings for Büchi complementation
• On the power of unambiguity in Büchi complementation
• On-the-Fly Stuttering in the Construction of Deterministic ω-Automata
• Reducing (To) the Ranks: Efficient Rank-Based Büchi Automata Complementation
• Seminator 2 can complement generalized Büchi automata via improved semi-determinization
• Simulations in rank-based Büchi automata complementation
• State of Büchi complementation
• The complementation problem for Büchi automata with applications to temporal logic
• Weak alternating automata are not that weak

Cited in

(2)

• Modular mix-and-match complementation of Büchi automata
• Complementation of Emerson-Lei automata

This page was built for publication: Sky is not the limit. Tighter rank bounds for elevator automata in Büchi automata complementation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535611)