133 citations · 155 across the 27 of their papers we have counts for
5 papers · 1 filter
Solving Streett and Emerson-Lei Games with Universal Trees
Daniel Hausmann, Marcin Jurdzinski, Nir Piterman
Nearly a decade ago, Calude et al. showed that parity games can be solved in quasi-polynomial time. This result is now understood in terms of universal trees. By reduction to parit…
Faster and Smaller Solutions of Obliging Games
Daniel Hausmann, Nir Piterman
Obliging games have been introduced in the context of the game perspective on reactive synthesis in order to enforce a degree of cooperation between the to-be-synthesized system an…
Doubly Fair Parity Games
Daniel Hausmann, Nir Piterman, Irmak Sağlam +1
We consider two-player games over finite graphs in which both players are restricted by fairness constraints on their moves. Given a two player game graph and a set of fa…
The Rabin index of parity games
Michael Huth, Jim Huan-Pu Kuo, Nir Piterman
We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colored game graphs are iden…
Algorithms for Büchi Games
Krishnendu Chatterjee, Thomas A. Henzinger, Nir Piterman
The classical algorithm for solving Büchi games requires time for game graphs with states and edges. For game graphs with constant outdegree, the best known a…