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;]

---

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

Shibashis Guha ; Ismaël Jecker ; Karoliina Lehtinen ; Martin Zimmermann.

We study the expressiveness and succinctness of history-deterministic pushdown automata (HD-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. These are also known as&nbsp;[&hellip;]

---