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.
ISSN 0988-3754, 1290-385X
|
Text
maxregulardelay_journal.pdf - Author Accepted Manuscript Download (574kB) | Preview |
Abstract
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: | 07 Dec 2024 09:12 |
| DOI: | 10.1051/ita/2016018 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3050011 |
Altmetric
Altmetric
