The Rabin index of parity games: its complexity and approximation

DOI10.1016/J.IC.2015.06.005MaRDI QIDQ897647zbMATH OpenOpenAlexFDO

Authors Michael Huth, Jim Huan-Pu Kuo, Nir Piterman

Publication date 7 December 2015

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ic.2015.06.005

zbMATH Keywords

logic in computer sciencecomputational difficulty of problemsdescriptive complexityparity gamespaths and cyclesRabin indexspecification and verificationgame graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 7356850
• Automata, Languages and Programming
• The Descriptive Complexity of Parity Games
• A randomized subexponential algorithm for parity games
• Parity games with partial information played on graphs of bounded complexity
• The complexity of partial-observation parity games
• A recursive approach to solving parity games in quasipolynomial time
• The parameterized complexity of positional games
• The banzhaf – coleman index for games withralternatives

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?)
• Computing the Rabin Index of a Parity Automaton
• DAG-Width and Parity Games
• Fatal Attractors in Parity Games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• On the Complexity of Timetable and Multicommodity Flow Problems
• On ω-regular sets
• Solving parity games in practice
• The directed subgraph homeomorphism problem

Cited in

(4)

• scientific article; zbMATH DE number 6490915 (Why is no real title available?)
• Computing the Rabin Index of a Parity Automaton
• scientific article; zbMATH DE number 7356850 (Why is no real title available?)
• Partial solvers for parity games: effective polynomial-time composition

Describes a project that uses

Uses Software

• PGSolver

This page was built for publication: The Rabin index of parity games: its complexity and approximation

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