1 citations · 2 across the 9 of their papers we have counts for
10 papers
Greedy Vector Balancing
Wojciech Czerwiński, Daniel Dadush, Ekin Ergen +3
In online vector balancing, vectors arrive one by one from a given set and the goal is to assign signs in an online manner so as to m…
Representing One Letter Weighted Automata Over the Tropical Semiring
Shaull Almagor, Ismaël Jecker, Filip Mazowiecki +3
We consider weighted automata over the tropical semiring . Recently, it was shown that determinisation is decidable; in this paper we focus on the comple…
Reachability in VASS Extended with Integer Counters
Clotilde Bizière, Wojciech Czerwiński, Roland Guttenberg +5
We consider a variant of VASS extended with integer counters, denoted VASS+Z. These are automata equipped with N and Z counters; the N-counters are required to remain nonnegative a…
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…
New Lower Bounds for Reachability in Vector Addition Systems
Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota +2
We investigate the dimension-parametric complexity of the reachability problem in vector addition systems with states (VASS) and its extension with pushdown stack (pushdown VASS).…
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…