3 papers
cs.GT2026
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…
cs.LO2020
A symmetric attractor-decomposition lifting algorithm for parity games
Marcin Jurdziński, Rémi Morvan, Pierre Ohlmann +1
Progress-measure lifting algorithms for solving parity games have the best worst-case asymptotic runtime, but are limited by their asymmetric nature, and known from the work of Cze…
cs.DS2020
The Strahler number of a parity game
Laure Daviaud, Marcin Jurdziński, K. S. Thejaswini
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smalles…