Tighter Bounds for the Determinisation of Büchi Automata

DOI10.1007/978-3-642-00596-1_13zbMath1234.68239OpenAlexW1528149868MaRDI QIDQ3617728

Sven Schewe

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_13

Mathematics Subject Classification ID

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

Related Items

Ramsey-Based Inclusion Checking for Visibly Pushdown Automata, From LTL to deterministic automata. A safraless compositional approach, Automata Theory and Model Checking, Solving parity games in big steps, Safraless LTL synthesis considering maximal realizability, Index appearance record with preorders, A survey on satisfiability checking for the \(\mu \)-calculus through tree automata, Profile trees for Büchi word automata, with application to determinization, Unnamed Item, New Optimizations and Heuristics for Determinization of Büchi Automata, Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis, Index Appearance Record for Transforming Rabin Automata into Parity Automata, Strategic reasoning with a bounded number of resources: the quest for tractability, Parametric linear dynamic logic, A Decision Procedure for CTL* Based on Tableaux and Automata, On the complexity of resource-bounded logics, A tighter analysis of Piterman's Büchi determinization, Unnamed Item, Program repair without regret, CEGAR for compositional analysis of qualitative properties in Markov decision processes, \( \omega \)-automata, Model Checking Omega-regular Properties for Quantum Markov Chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• A tighter analysis of Piterman's Büchi determinization
• Asymptotic Estimates of Stirling Numbers
• Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
• Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• BÜCHI COMPLEMENTATION MADE TIGHTER
• Solving Sequential Conditions by Finite-State Strategies
• Definability in the monadic second-order theory of successor
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Alternating tree automata, parity games, and modal \(\mu\)-calculus