A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata

DOI10.1007/978-3-642-02930-1_13MaRDI QIDQ3638092zbMATH OpenOpenAlexFDO

Authors Thomas Colcombet, Konrad Zdanowski

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Tighter Bounds for the Determinisation of Büchi Automata
• Tight Bounds for the Determinisation and Complementation of Generalised Büchi Automata
• Determinization of Büchi-Automata
• Implementation and Application of Automata
• Observations on determinization of Büchi automata
• On Transition Minimality of Bideterministic Automata
• ON TRANSITION MINIMALITY OF BIDETERMINISTIC AUTOMATA
• Determinization of Büchi automata: unifying the approaches of Safra and Muller-Schupp
• Deternimization of Büchi automata as partitioned automata
• From LTL and limit-deterministic Büchi automata to deterministic parity automata

Cited in

(16)

• -automata
• The mu-calculus and Model Checking
• New optimizations and heuristics for determinization of Büchi automata
• ON TRANSITION MINIMALITY OF BIDETERMINISTIC AUTOMATA
• Tighter Bounds for the Determinisation of Büchi Automata
• Tight Bounds for the Determinisation and Complementation of Generalised Büchi Automata
• Rabin vs. Streett automata
• Improved upper and lower bounds for Büchi disambiguation
• The logical strength of Büchi's decidability theorem
• On Transition Minimality of Bideterministic Automata
• On the translation of automata to linear temporal logic
• Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition
• From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
• Optimal transformations of games and automata using Muller conditions
• Lower bound for the number of states of purposeful deterministic automata
• A tighter analysis of Piterman's Büchi determinization

This page was built for publication: A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata

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