|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Unbounded Lookahead in WMSO+U Games | | Martin Zimmermann
; | | Date: |
24 Sep 2015 | | 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 (WMSO+U), which is able to express
(un)boundedness properties. It is decidable whether the delaying player is able
to win such a game with bounded lookahead, i.e., if she only skips a finite
number of moves.
However, bounded lookahead is not always sufficient: we present a game that
can be won with unbounded lookahead, but not with bounded lookahead. Then, we
consider WMSO+U delay games with unbounded lookahead and show that the exact
evolution of the lookahead is irrelevant. Finally, we investigate whether the
winner of such a game with unbounded lookahead is effectively computable: we
reduce this problem to a delay-free infinite game with WMSO+U winning
condition, whose winner is effectively computable. However, we only obtain
partial results on the effectiveness of the reduction, thereby leaving
decidability also open. | | Source: | arXiv, 1509.7495 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER