19 citations · 53 across the 15 of their papers we have counts for
16 papers · 1 filter
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…
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…
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…
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…