1 citations · 1 across the 2 of their papers we have counts for
6 papers
Exploring VASS Parameterised by Geometric Dimension
Wojciech Czerwiński, Roland Guttenberg, Łukasz Orlikowski +2
The geometric dimension of a Vector Addition System with States (VASS) is the dimension of the vector space generated by cycles in the VASS; this parameter refines the standard…
Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
Wojciech Czerwiński, Łukasz Orlikowski
In this work, we extend undecidability of language equivalence for two-dimensional Vector Addition System with States (VASS) accepting by coverability condition. We show that the p…
Languages of Boundedly-Ambiguous Vector Addition Systems with States
Wojciech Czerwiński, Łukasz Orlikowski
The aim of this paper is to deliver broad understanding of a class of languages of boundedly-ambiguous VASS, that is k-ambiguous VASS for some natural k. These are languages of Vec…
Reachability in 3-VASS is Elementary
Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota +1
The reachability problem in 3-dimensional vector addition systems with states (3-VASS) is known to be PSpace-hard, and to belong to Tower. We significantly narrow down the complexi…
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…
Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
Wojciech Czerwiński, Łukasz Orlikowski
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…