26 citations · 68 across the 9 of their papers we have counts for
5 papers · 1 filter
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…
Undecidability of a weak version of MSO+U
Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon +2
We prove the undecidability of MSO on -words extended with the second-order predicate which says that the distance between consecutive positions in a set $X \subseteq \…
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…