19 citations · 53 across the 15 of their papers we have counts for
20 papers
The Tractability Border of Reachability in Simple Vector Addition Systems with States
Dmitry Chistikov, Wojciech Czerwiński, Filip Mazowiecki +3
Vector Addition Systems with States (VASS), equivalent to Petri nets, are a well-established model of concurrency. The central algorithmic challenge in VASS is the reachability pro…
Languages given by Finite Automata over the Unary Alphabet
Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz +5
This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary. Let denote the maximum of the numbe…
Long Runs Imply Big Separators in Vector Addition Systems
Wojciech Czerwiński, Adam Jędrych
Despite recent progress which settled the complexity of the reachability problem for Vector Addition Systems with States (VASSes) as being Ackermann-complete we still lack much und…
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…
Unboundedness problems for languages of vector addition systems
Wojciech Czerwiński, Piotr Hofman, Georg Zetzsche
A vector addition system (VAS) with an initial and a final marking and transition labels induces a language. In part because the reachability problem in VAS remains far from being…
Regular Separability of One Counter Automata
Wojciech Czerwiński, Sławomir Lasota
The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other. Our main result is decidabilit…
Regular Separability of Parikh Automata
Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota +1
We investigate a subclass of languages recognized by vector addition systems, namely languages of nondeterministic Parikh automata. While the regularity problem (is the language of…
Separability of Reachability Sets of Vector Addition Systems
Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota +1
Given two families of sets and , the separability problem for asks whether for two given sets there ex…
Shortest paths in one-counter systems
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2
We show that any one-counter automaton with states, if its language is non-empty, accepts some word of length at most . This closes the gap between the previously known…
Non-dominating sequences of vectors using only resets and increments
Wojciech Czerwinski, Tomasz Gogacz, Eryk Kopczynski
We consider a variant of Dickson lemma, where each entry of a vector can be reseted or incremented by 1 in respect to the previous one. We give an example of non dominating sequenc…
A Characterization for Decidable Separability by Piecewise Testable Languages
Wojciech Czerwiński, Wim Martens, Lorijn van Rooijen +2
The separability problem for word languages of a class by languages of a class asks, for two given languages and from , whether the…
Branching Bisimilarity of Normed BPA Processes is in NEXPTIME
Wojciech Czerwiński, Petr Jančar
Branching bisimilarity on normed BPA processes was recently shown to be decidable by Yuxi Fu (ICALP 2013) but his proof has not provided any upper complexity bound. We present a si…
Reachability Problem for Weak Multi-Pushdown Automata
Wojciech Czerwiński, Piotr Hofman, SŁawomir Lasota
This paper is about reachability analysis in a restricted subclass of multi-pushdown automata. We assume that the control states of an automaton are partially ordered, and all tran…
Efficient Separability of Regular Languages by Subsequences and Suffixes
Wojciech Czerwiński, Wim Martens, Tomáš Masopust
When can two regular word languages K and L be separated by a simple language? We investigate this question and consider separation by piecewise- and suffix-testable languages and…
Partially-commutative context-free languages
Wojciech Czerwiński, Sławomir Lasota
The paper is about a class of languages that extends context-free languages (CFL) and is stable under shuffle. Specifically, we investigate the class of partially-commutative conte…