Minimizing GFG Transition-Based Automata

DOI10.4230/LIPIcs.ICALP.2019.100OpenAlexW2966079298MaRDI QIDQ5091262

Radi Bader abu, Orna Kupferman

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10676/pdf/LIPIcs-ICALP-2019-100.pdf

zbMATH Keywords

minimizationdeterministic co-Büchi automata

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items

Unnamed Item, A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct, Minimization of automata for liveness languages, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing finite automata is computationally hard
• Reasoning about infinite computations
• STACS 98. 15th annual symposium on theoretical aspects of computer science. Paris, France, February 25--27, 1998. Proceedings
• Efficient minimization of deterministic weak \(\omega\)-automata
• Fair simulation
• Relating word and tree automata
• Beyond Hyper-Minimisation--Minimising DBAs and DPAs is NP-Complete
• Linear Automaton Transformations
• On Determinisation of Good-for-Games Automata
• Hyper-minimizing minimized deterministic finite state automata
• The Theory of Stabilisation Monoids and Regular Cost Functions
• Minimal NFA Problems are Hard
• Limit-Deterministic Büchi Automata for Linear Temporal Logic
• Büchi Good-for-Games Automata Are Efficiently Recognizable
• How Deterministic are Good-For-Games Automata?
• Nondeterminism in the Presence of a Diverse or Unknown Future
• HYPER-MINIMIZATION FOR DETERMINISTIC TREE AUTOMATA
• Lattice Automata
• Decision problems forω-automata
• Depth-First Search and Linear Graph Algorithms
• Minimizing Deterministic Lattice Automata