Search

• < Previous
• 1
• Next >

---

Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width

John Fearnley ; Sven Schewe.

Parity games are a much researched class of games in NP intersect CoNP that are not known to be in P. Consequently, researchers have considered specialised algorithms for the case where certain graph parameters are small. In this paper, we study parity games on graphs with bounded treewidth, and&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;]

---

A Recursive Approach to Solving Parity Games in Quasipolynomial Time

Karoliina Lehtinen ; Paweł Parys ; Sven Schewe ; Dominik Wojtczak.

Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of&nbsp;[&hellip;]

---

History-deterministic Timed Automata

Sougata Bose ; Thomas A. Henzinger ; Karoliina Lehtinen ; Sven Schewe ; Patrick Totzke.

We explore the notion of history-determinism in the context of timed automata (TA) over infinite timed words. History-deterministic (HD) automata are those in which nondeterminism can be resolved on the fly, based on the run constructed thus far. History-determinism is a robust property that admits&nbsp;[&hellip;]

---