Partial solvers for parity games: effective polynomial-time composition

MaRDI QIDQ5015265zbMATH OpenFDO

Authors Patrick Ah-Fat, Michael Huth

Publication date 7 December 2021

Full work available at URL https://arxiv.org/abs/1609.04085, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2016.1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Recommendations

• Static analysis of parity games: alternating reachability under parity
• Solving parity games in practice
• Fatal Attractors in Parity Games
• Improving parity games in practice
• Graph operations on parity games and polynomial-time algorithms

Cites work

• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• A deterministic subexponential algorithm for solving parity games
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• DAG-Width and Parity Games
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Entanglement and the complexity of directed graphs
• Fatal Attractors in Parity Games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Recursive algorithm for parity games requires exponential time
• Solving parity games in practice
• Static analysis of parity games: alternating reachability under parity
• The Rabin index of parity games: its complexity and approximation
• Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width

Cited in

(1)

• Static analysis of parity games: alternating reachability under parity

Describes a project that uses

Uses Software

• PGSolver

This page was built for publication: Partial solvers for parity games: effective polynomial-time composition

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