Memoryless determinacy of parity and mean payoff games: a simple proof

DOI10.1016/S0304-3975(03)00427-4zbMath1098.91027MaRDI QIDQ1884982

Sven Sandberg, Henrik Björklund, Sergei Vorobyov

Publication date: 27 October 2004

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

Mathematics Subject Classification ID

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 (13)

Looking at mean payoff through foggy windows ⋮ Mean-payoff games with partial observation ⋮ Solving parity games in big steps ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games ⋮ Average-energy games ⋮ Parameterized Algorithms for Parity Games ⋮ Memoryless determinacy of finite parity games: another simple proof ⋮ Unnamed Item ⋮ Cyclic games and linear programming ⋮ First-cycle games ⋮ Energy parity games ⋮ Combinatorial structure and randomized subexponential algorithms for infinite games

Cites Work

• Positional strategies for mean payoff games
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• The complexity of mean payoff games on graphs
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Decidability of Second-Order Theories and Automata on Infinite Trees
• On model checking for the \(\mu\)-calculus and its fragments
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Memoryless determinacy of parity and mean payoff games: a simple proof