Search

• < Previous
• 1
• Next >

---

Parity and Streett Games with Costs

Nathanaël Fijalkow ; Martin Zimmermann.

We consider two-player games played on finite graphs equipped with costs on edges and introduce two winning conditions, cost-parity and cost-Streett, which require bounds on the cost between requests and their responses. Both conditions generalize the corresponding classical omega-regular conditions&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;]

---

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

---

Parity Games with Weights

Sven Schewe ; Alexander Weinert ; Martin Zimmermann.

Quantitative extensions of parity games have recently attracted significant interest. These extensions include parity games with energy and payoff conditions as well as finitary parity games and their generalization to parity games with costs. Finitary parity games enjoy a special status among these&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;]

---

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

---