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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1962853 (Why is no real title available?)
- scientific article; zbMATH DE number 1500523 (Why is no real title available?)
- A deterministic subexponential algorithm for solving parity games
- Automata, logics, and infinite games. A guide to current research
- Borel determinacy
- Clique-Width and Parity Games
- DAG-Width and Parity Games
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Explicit Muller games are PTIME
- Facets of Synthesis: Revisiting Church’s Problem
- Fast mu-calculus model checking when tree-width is bounded.
- Fixed-point logics and solitaire games
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- Solving Parity Games in Big Steps
Cited in
(4)
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)
