Search

• < Previous
• 1
• Next >

---

How Much Lookahead is Needed to Win Infinite Games?

Felix Klein ; Martin Zimmermann.

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. For $\omega$-regular winning conditions it is known that such games can be solved in doubly-exponential time and that doubly-exponential lookahead is&nbsp;[&hellip;]

---

Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs

Alexander Weinert ; Martin Zimmermann.

The winning condition of a parity game with costs requires an arbitrary, but fixed bound on the cost incurred between occurrences of odd colors and the next occurrence of a larger even one. Such games quantitatively extend parity games while retaining most of their attractive properties, i.e,&nbsp;[&hellip;]

---

Good-for-games $\omega$-Pushdown Automata

Karoliina Lehtinen ; Martin Zimmermann.

We introduce good-for-games $\omega$-pushdown automata ($\omega$-GFG-PDA). These are automata whose nondeterminism can be resolved based on the input processed so far. Good-for-gameness enables automata to be composed with games, trees, and other automata, applications which otherwise require&nbsp;[&hellip;]

---