56 citations · 207 across the 8 of their papers we have counts for
15 papers
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow +3
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and St…
When is Containment Decidable for Probabilistic Automata?
Laure Daviaud, Marcin Jurdziński, Ranko Lazić +3
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean au…
Perfect Half Space Games
Thomas Colcombet, Marcin Jurdziński, Ranko Lazić +1
We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional weights diverge in a direction which is consistent with a…
Succinct progress measures for solving parity games
Marcin Jurdzinski, Ranko Lazic
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly sub…
Mean-Payoff Games on Timed Automata
Shibashis Guha, Marcin Jurdzinski, Krishna S. +1
Mean-payoff games on timed automata are played on the infinite weighted graph of configurations of priced timed automata between two players, Player Min and Player Max, by moving a…
Distributed Methods for Computing Approximate Equilibria
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis +3
We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same t…