5 citations · 6 across the 4 of their papers we have counts for
6 papers
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…
Fast Obligation Translation and Synthesis
Alexandre Duret-Lutz, Giuseppe De Giacomo, Marcin Jurdzinski +3
Syntactic obligations are a fragment of LTL formulas that translate to deterministic weak -automata (DWA). We show that syntactic obligations can be very efficiently converted t…
Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata
Rohan Acharya, Marcin Jurdziński, Keya Prakash
Our main technical contribution is a polynomial-time determinisation procedure for history-deterministic Büchi automata, which settles an open question of Kuperberg and Skrzypczak,…
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…
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…
Universal Algorithms for Parity Games and Nested Fixpoints
Marcin Jurdziński, Rémi Morvan, K. S. Thejaswini
An attractor decomposition meta-algorithm for solving parity games is given that generalises the classic McNaughton-Zielonka algorithm and its recent quasi-polynomial variants due…