5 papers
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 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…
Regular and First Order List Functions
Mikolaj Bojanczyk, Laure Daviaud, Krishna Shankara Narayanan
We define two classes of functions, called regular (respectively, first-order) list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pair…
A pseudo-quasi-polynomial algorithm for solving mean-payoff parity games
Laure Daviaud, Marcin Jurdzinski, Ranko Lazic
In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payo…