56 citations · 231 across the 17 of their papers we have counts for
4 papers · 1 filter
The Reachability Problem for Petri Nets is Not Elementary
Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic +2
Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and datab…
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…
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…