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

---

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

---