
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. Recently, such games with quantitative winning conditions in weak MSO with the unbounding quantifier were studied, but their properties turned out to be unsatisfactory. In particular, unbounded lookahead is in general necessary. Here, we study delay games with winning conditions given by Prompt-LTL, Linear Temporal Logic equipped with a parameterized eventually operator whose scope is bounded. Our main result shows that solving Prompt-LTL delay games is complete for triply-exponential time. Furthermore, we give tight triply-exponential bounds on the necessary lookahead and on the scope of the parameterized eventually operator. Thus, we identify Prompt-LTL as the first known class of well-behaved quantitative winning conditions for delay games. Finally, we show that applying our techniques to delay games with ��-regular winning conditions answers open questions in the cases where the winning conditions are given by non-deterministic, universal, or alternating automata.
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Prompt-LTL, 004, Logic in Computer Science (cs.LO), Computer Science - Computer Science and Game Theory, Delay Games, Infinite Games, LTL, Computer Science and Game Theory (cs.GT), ddc: ddc:004
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Prompt-LTL, 004, Logic in Computer Science (cs.LO), Computer Science - Computer Science and Game Theory, Delay Games, Infinite Games, LTL, Computer Science and Game Theory (cs.GT), ddc: ddc:004
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
