An O(n^2) time algorithm for alternating Büchi games
From MaRDI portal
Recommendations
- Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
- Conditionally Optimal Algorithms for Generalized B\"uchi Games
- Computer Science Logic
- Improved algorithms for parity and Streett objectives
- Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives
Cites work
- Alternating-time temporal logic
- Alternation
- An On-Line Edge-Deletion Problem
- AND/OR graph heuristic search methods
- Automata-Theoretic Model Checking Revisited
- Computer Science Logic
- Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
- Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification
- From linear time to branching time
- scientific article; zbMATH DE number 4124989 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (Why is no real title available?)
- scientific article; zbMATH DE number 1948169 (Why is no real title available?)
- scientific article; zbMATH DE number 2080757 (Why is no real title available?)
- scientific article; zbMATH DE number 1500523 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3237829 (Why is no real title available?)
- scientific article; zbMATH DE number 3189696 (Why is no real title available?)
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- Number of quantifiers is better than number of tape cells
- On the menbership problem for functional and multivalued dependencies in relational databases
- Quantitative stochastic parity games
- Solving Sequential Conditions by Finite-State Strategies
- Supervisory Control of a Class of Discrete Event Processes
- The Büchi Complementation Saga
- The complexity of probabilistic verification
- The complexity of stochastic games
- Weak Second‐Order Arithmetic and Finite Automata
Cited in
(18)- Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
- Qualitative analysis of concurrent mean-payoff games
- Optimal cost almost-sure reachability in POMDPs
- Games for query inseparability of description logic knowledge bases
- Knowledge base exchange: the case of OWL 2 QL
- Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
- Efficient algorithms for games played on trees with back-edges
- Trading performance for stability in Markov decision processes
- Conditionally Optimal Algorithms for Generalized B\"uchi Games
- Of cores: a partial-exploration framework for Markov decision processes
- Petri games: synthesis of distributed systems with causal memory
- Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components
- Quantitative fair simulation games
- Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification
- Near-linear time algorithms for Streett objectives in graphs and MDPs
- A survey on satisfiability checking for the \(\mu \)-calculus through tree automata
- Assume-guarantee synthesis for digital contract signing
- CEGAR for compositional analysis of qualitative properties in Markov decision processes
This page was built for publication: An \(O(n^2)\) time algorithm for alternating Büchi games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743484)
