The Rabin index of parity games: its complexity and approximation

DOI10.1016/J.IC.2015.06.005zbMath1332.68060OpenAlexW1917713630MaRDI QIDQ897647

Jim Huan-Pu Kuo, Nir Piterman, Michael Huth

Publication date: 7 December 2015

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

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

zbMATH Keywords

parity gameslogic in computer sciencecomputational difficulty of problemsdescriptive complexitypaths and cyclesRabin indexspecification and verificationgame graphs

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Uses Software

• PGSolver

Cites Work

• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Solving Parity Games in Practice
• On ω-regular sets
• On the Complexity of Timetable and Multicommodity Flow Problems
• Fatal Attractors in Parity Games
• Computing the Rabin Index of a Parity Automaton
• DAG-Width and Parity Games

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