Wojciech Czerwiński

Highlights Conference 2025 Conference Abstract

Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable

• Wojciech Czerwiński

Highlights Conference 2024 Conference Abstract

Reachability in binary 3-VASS is in ExpSpace

• Wojciech Czerwiński

We consider the reachability problem for Vector Addition Systems with States (VASS) in dimension three. In the dimension two the problem is known to be PSpace-complete since 2015. However, already for three-dimensional VASS (3-VASS) there is a huge gap in understanding of the complexity and currently the problem is only known to be PSpace-hard and in Tower. We show that the reachability problem in binary 3-VASS (a 3-VASS with numbers on transitions encoded in binary) can be decided in exponential space. This does not fix the complexity, but substantially improves the upper bound. Our main contribution states that if there is a path between two its configurations then there is also a path of at most doubly-exponential length, which immediately implies an ExpSpace algorithm. It is challenging to obtain below-Tower complexity as there exists 3-VASS of finite, but almost Tower-big reachability sets (concretely speaking k-fold exponential, for any k ∈ N). We introduce a novel technique of sandwiching reachability sets between two semilinear sets, which have small representation and behave similarly. This intuitively allows us to deal with big, finite sets in time faster than their size. We also make use of recent results about the form of reachability paths in 2-VASS, sequential cones and other techniques. The presentation is based on a joint work with Ismael Jecker, Sławomir Lasota and Łukasz Orlikowski.

Highlights Conference 2022 Conference Abstract

Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

• Wojciech Czerwiński

We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-the-art: 1) NP-hardness for unary flat 3-VASSes (VASSes in dimension 3), 2) PSpace-hardness for unary 5-VASSes, 3) ExpSpace-hardness for binary 6-VASSes and 4) Tower-hardness for unary 8-VASSes. On the presentation I plan to tell a few words about 1) the results, 2) techniques, which we have used, 3) motiviations to study low dimensional VASSes, and 4) important challenges, which remain for the future. Previous version of this work was submitted to LICS 2022, a co-autor is Łukasz Orlikowski. The work is on arXiv.

Highlights Conference 2021 Conference Abstract

Reachability in Vector Addition Systems is Ackermann-complete

• Wojciech Czerwiński

Vector Addition Systems and equivalent Petri nets are a well established models of concurrency. The central algorithmic problem for Vector Addition Systems with a long research history is the reachability problem asking whether there exists a run from one given configuration to another. We settle its complexity to be Ackermann-complete thus closing the problem open for 45 years. In particular we prove that the problem is -hard for Vector Addition Systems with States in dimension, where is the -th complexity class from the hierarchy of fast-growing complexity classes.

Highlights Conference 2020 Conference Abstract

Universality Problem for Unambiguous VASS

• Wojciech Czerwiński

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 defined by a set of final states (i. e. , the coverability language). We show that the problem of universality for unambiguous VASS is ExpSpace-complete, in sheer contrast to Ackermann-completeness for arbitrary VASS, even in dimension 1. When the dimension d ∈ N is fixed, the universality problem is PSpace-complete if d ≥ 2, and coNP-hard for 1-dimensional VASSes (also known as One Counter Nets).

Highlights Conference 2018 Conference Abstract

The Reachability Problem for Vector Addition Systems is Not Elementary

• Wojciech Czerwiński

ABSTRACT. The reachability problem for Vector Addition Systems is currently known to be decidable (best upper bound is cubic-Ackermann) and ExpSpace-hard. We provide a better lower bound showing that in fact problem is not elementary. The construction is based on the observation that certain kind of fraction equations can have surprisingly involved solutions and Vector Addition Systems are able to implement that phenomenon.

Highlights Conference 2017 Conference Abstract

Regular Separability of One Counter Automata

• Wojciech Czerwiński

Abstract available in PDF.

Highlights Conference 2016 Conference Abstract

Separability of Reachability Sets of Vector Addition Systems

• Wojciech Czerwiński

The separability problem of sets from a class G by a set from a class F asks whether for two given sets U, V in G there exists a set S in F such that U is included in S and V has an empty intersection with S. We show that separability problem of reachability sets of Vector Addition Systems by both modular and unary sets is decidable.

Highlights Conference 2015 Conference Abstract

The (Almost) Complete Guide to Tree Pattern Containment

• Wojciech Czerwiński

Tree pattern queries are being investigated in database theory for more than a decade. They are a fundamental and flexible query mechanism and have been considered in the context of querying tree structured as well as graph structured data. We revisit their containment, validity, and satisfiability problem, both with and without schema information. We present a comprehensive overview of what is known about the complexity of containment and develop new techniques which allow us to obtain tractability and hardness results for cases that have been open since the early work on tree pattern containment. For the tree pattern queries we consider in this paper, it is known that the containment problem does not depend on whether patterns are evaluated on trees or on graphs. This means that our results also shed new light on tree pattern queries on graphs.

Highlights Conference 2014 Conference Abstract

Separability of Context-Free Languages by Piecewise Testable Languages

• Wojciech Czerwiński

Language S separates languages K and L if S contains K and has empty an intersection with L. We show the decidability of the following question: given two context-free languages, does there exists a piecewise testable language which separates them? It is known that separating context-free languages is undecidable for all classes containing definite languages. Therefore the class of piecewise testable languages seems to be the first nontrivial class of languages for which the above problem is decidable.

Highlights Conference 2013 Conference Abstract

Efficient separability of regular languages by subsequences and suffixes

• Wojciech Czerwiński
• Wim Martens
• Tomas 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 variants thereof. We give characterizations of when two languages can be separated and present an overview of when these problems can be decided in polynomial time if K and L are given by nondeterministic automata.