Memoryless determinacy of infinite parity games: another simple proof

DOI10.1016/J.IPL.2018.10.015MaRDI QIDQ1711414zbMATH OpenOpenAlexWikidataFDO

Authors Stéphane Le Roux

Publication date 18 January 2019

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

(transfinite) inductionfinitely many prioritiesformal methodsinfinite graphpositional determinacy

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43)

Abstract: In 1998 Zielonka simplified the proofs of memoryless determinacy of infinite parity games. In 2018 Haddad simplified some proofs of memoryless determinacy of finite parity games. This article adapts Haddad's technique for infinite parity games. Two proofs are given, a shorter one and a more constructive one. None of them uses Zielonka's traps and attractors.

Recommendations

• Memoryless determinacy of finite parity games: another simple proof
• Memoryless determinacy of parity and mean payoff games: a simple proof
• Memoryless Determinacy of Parity Games
• On the positional determinacy of edge-labeled games
• Positional Determinacy of Games with Infinitely Many Priorities

Cites work

• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Memoryless determinacy of finite parity games: another simple proof
• Positional Determinacy of Games with Infinitely Many Priorities

Cited in

(5)

• Memoryless determinacy of finite parity games: another simple proof
• Memoryless determinacy of parity and mean payoff games: a simple proof
• Unforgettable Forgetful Determinacy
• Memoryless Determinacy of Parity Games
• First-cycle games

This page was built for publication: Memoryless determinacy of infinite parity games: another simple proof

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