Partial solvers for parity games: effective polynomial-time composition

zbMATH Open1478.68139arXiv1609.04085MaRDI QIDQ5015265FDOQ5015265

Authors: Patrick Ah-Fat, Michael Huth 

Publication date: 7 December 2021

Full work available at URL: https://arxiv.org/abs/1609.04085

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

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)

Cites Work

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

Cited In (1)

• Static analysis of parity games: alternating reachability under parity

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)