Delay Games with WMSO+U Winning Conditions

Zimmermann, Martin ORCID: 0000-0002-8038-2453
(2014) Delay Games with WMSO+U Winning Conditions. RAIRO - Theoretical Informatics and Applications, 50 (2). pp. 145-165.

[img] Text
maxregulardelay_journal.pdf - Author Accepted Manuscript

Download (574kB) | Preview


Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent's moves. We consider delay games with winning conditions expressed in weak monadic second order logic with the unbounding quantifier, which is able to express (un)boundedness properties. We show that it is decidable whether the delaying player has a winning strategy using bounded lookahead and give a doubly-exponential upper bound on the necessary lookahead. In contrast, we show that bounded lookahead is not always sufficient to win such a game.

Item Type: Article
Additional Information: A short version appears in the proceedings of CSR 2015. The definition of the equivalence relation introduced in Section 3 is updated: the previous one was inadequate, which invalidates the proof of Lemma 2. The correction presented here suffices to prove Lemma 2 and does not affect our main theorem. arXiv admin note: text overlap with arXiv:1412.3701
Uncontrolled Keywords: cs.GT, cs.GT, cs.FL
Depositing User: Symplectic Admin
Date Deposited: 15 Jul 2019 13:06
Last Modified: 19 Jan 2023 00:37
DOI: 10.1051/ita/2016018
Related URLs: