3 citations · 4 across the 4 of their papers we have counts for
9 papers
Universality Problem for Unambiguous VASS
Wojciech Czerwiński, Diego Figueira, Piotr Hofman
We study languages of unambiguous VASS, that is, Vector Addition Systems with States, whose transitions read letters from a finite alphabet, and whose acceptance condition is defin…
An Approach to Regular Separability in Vector Addition Systems
Wojciech Czerwiński, Georg Zetzsche
We study the problem of regular separability of languages of vector addition systems with states (VASS). It asks whether for two given VASS languages K and L, there exists a regula…
New Pumping Technique for 2-dimensional VASS
Wojciech Czerwiński, Sławomir Lasota, Christof Löding +1
We propose a new pumping technique for 2-dimensional vector addition systems with states (2-VASS) building on natural geometric properties of runs. We illustrate its applicability…
Improved bounds for the excluded-minor approximation of treedepth
Wojciech Czerwiński, Wojciech Nadara, Marcin Pilipczuk
Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant …
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…