Alternating traps in Muller and parity games

DOI10.1016/j.tcs.2013.11.032zbMath1394.91060arXiv1303.3777OpenAlexW2165296213MaRDI QIDQ389948

Andrei Tarfulea, Andrey Grinshpun, Sasha Rubin, Pakawat Phalitnonkiat

Publication date: 22 January 2014

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

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

zbMATH Keywords

parity gamesMuller games

Mathematics Subject Classification ID

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

Related Items (2)

Deciding Parity Games in Quasi-polynomial Time ⋮ First-cycle games

Cites Work

• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Borel determinacy
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• Fixed-point logics and solitaire games
• Automata, logics, and infinite games. A guide to current research
• Explicit Muller Games are PTIME
• A deterministic subexponential algorithm for solving parity games
• Clique-Width and Parity Games
• Facets of Synthesis: Revisiting Church’s Problem
• DAG-Width and Parity Games
• Solving Parity Games in Big Steps
• Computer Aided Verification

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