Solving Parity Games in Big Steps
From MaRDI portal
Publication:5458856
DOI10.1007/978-3-540-77050-3_37zbMath1135.68480OpenAlexW1526785305MaRDI QIDQ5458856
Publication date: 24 April 2008
Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_37
Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
Symmetric Strategy Improvement ⋮ The mu-calculus and Model Checking ⋮ Graph Games and Reactive Synthesis ⋮ Cooking Your Own Parity Game Preorders Through Matching Plays ⋮ From Parity and Payoff Games to Linear Programming ⋮ Solving parity games in big steps ⋮ Parity game reductions ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Model-checking iterated games ⋮ Latticed-LTL synthesis in the presence of noisy inputs ⋮ Deciding the unguarded modal -calculus ⋮ Parameterized linear temporal logics meet costs: still not costlier than LTL ⋮ Alternating traps in Muller and parity games ⋮ Robust worst cases for parity games algorithms ⋮ Parameterized Algorithms for Parity Games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A superpolynomial lower bound for strategy iteration based on snare memorization ⋮ Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis ⋮ CADP 2010: A Toolbox for the Construction and Analysis of Distributed Processes ⋮ Solving parity games via priority promotion ⋮ The Modal μ-Calculus Caught Off Guard ⋮ New deterministic algorithms for solving parity games ⋮ A Multi-Core Solver for Parity Games ⋮ A Decision Procedure for CTL* Based on Tableaux and Automata ⋮ Verification of reactive systems via instantiation of parameterised Boolean equation systems ⋮ A delayed promotion policy for parity games ⋮ Solving μ-Calculus Parity Games by Symbolic Planning ⋮ Improving parity games in practice ⋮ How Much Lookahead is Needed to Win Infinite Games? ⋮ How Much Lookahead is Needed to Win Infinite Games? ⋮ Solving Parity Games Using an Automata-Based Algorithm ⋮ Solving Parity Games in Practice ⋮ Recursive algorithm for parity games requires exponential time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Results on the propositional \(\mu\)-calculus
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- The complexity of mean payoff games on graphs
- An improved algorithm for the evaluation of fixpoint expressions
- A subexponential randomized algorithm for the simple stochastic game problem
- Alternating-time temporal logic
- A deterministic subexponential algorithm for solving parity games
- Synthesis of Asynchronous Systems
- Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
- DAG-Width and Parity Games
- Computer Aided Verification
- Alternating tree automata, parity games, and modal \(\mu\)-calculus
