Solving parity games by a reduction to SAT
DOI10.1016/J.JCSS.2011.05.004zbMATH Open1279.68211OpenAlexW2090204914MaRDI QIDQ414902FDOQ414902
Authors: Keijo Heljanko, Misa Keinänen, Martin Lange, Ilkka Niemelä 
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.05.004
Recommendations
- Solving parity games in practice
- Parity game reductions
- Solving parity games using an automata-based algorithm
- Solving parity games: explicit vs symbolic
- A CSP-Based Approach for Solving Parity Game
- Solving counter parity games
- Algorithms for solving parity games
- Solving parity games on integer vectors
- Solving parity games in big steps
- Solving Parity Games in Big Steps
Applications of game theory (91A80) 2-person games (91A05) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43) Logic in computer science (03B70)
Cites Work
- The complexity of mean payoff games on graphs
- Extending and implementing the stable model semantics
- Symbolic model checking: \(10^{20}\) states and beyond
- Linear Encodings of Bounded LTL Model Checking
- Verification of timed automata via satisfiability checking
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computer Aided Verification
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Notes on finite asynchronous automata
- On model checking for the \(\mu\)-calculus and its fragments
- Bounded model checking using satisfiability solving
- A subexponential randomized algorithm for the simple stochastic game problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bounded model checking for all regular properties
- On Nonterminating Stochastic Games
- A deterministic subexponential algorithm for solving parity games
- Tableau-based model checking in the propositional mu-calculus
- Fast and simple nested fixpoints
- Solving parity games by a reduction to SAT
- Title not available (Why is that?)
- Bounded Model Checking for Weak Alternating Büchi Automata
Cited In (11)
- Stable-unstable semantics: Beyond NP with normal logic programs
- Solving parity games by a reduction to SAT
- SAT modulo graphs: acyclicity
- Parity game reductions
- Solving parity games using an automata-based algorithm
- Parity to safety in polynomial time for pushdown and collapsible pushdown systems
- From Parity and Payoff Games to Linear Programming
- Winning Regions of Pushdown Parity Games: A Saturation Method
- Improving parity game solvers with justifications
- Title not available (Why is that?)
- A CSP-Based Approach for Solving Parity Game
Uses Software
This page was built for publication: Solving parity games by a reduction to SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414902)
