The Rabin index of parity games: its complexity and approximation

DOI10.1016/J.IC.2015.06.005zbMATH Open1332.68060OpenAlexW1917713630MaRDI QIDQ897647FDOQ897647

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

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

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
• scientific article; zbMATH DE number 7471697
• The parameterized complexity of positional games
• The banzhaf – coleman index for games withralternatives

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)

Cites Work

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

Cited In (4)

• Computing the Rabin Index of a Parity Automaton
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)