56 citations · 307 across the 14 of their papers we have counts for
3 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…
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…
Reachability in Two-Clock Timed Automata is PSPACE-complete
John Fearnley, Marcin Jurdziński
A recent result of Haase et al. has shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reacha…