Alternating traps in Muller and parity games

DOI10.1016/J.TCS.2013.11.032zbMATH Open1394.91060arXiv1303.3777OpenAlexW2165296213MaRDI QIDQ389948FDOQ389948

Authors: Andrey Grinshpun, Pakawat Phalitnonkiat, Sasha Rubin, Andrei Tarfulea 

Publication date: 22 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP and co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap-depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth.

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

Recommendations

• Deciding parity games in quasipolynomial time
• Algorithms for solving parity games
• Mathematical Foundations of Computer Science 2005
• Algorithms for Parity Games
• Explicit Muller games are PTIME

zbMATH Keywords

parity gamesMuller games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Cites Work

• Borel determinacy
• Automata, logics, and infinite games. A guide to current research
• Title not available (Why is that?)
• 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
• Infinite games played on finite graphs
• Title not available (Why is that?)
• DAG-Width and Parity Games
• Solving Parity Games in Big Steps
• Fast mu-calculus model checking when tree-width is bounded.
• A deterministic subexponential algorithm for solving parity games
• Fixed-point logics and solitaire games
• Explicit Muller games are PTIME
• Clique-Width and Parity Games
• Facets of Synthesis: Revisiting Church’s Problem

Cited In (4)

• Deciding Parity Games in Quasi-polynomial Time
• Playing Muller games in a hurry
• Fatal Attractors in Parity Games
• First-cycle games

This page was built for publication: Alternating traps in Muller and parity games

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