9 papers
Reachability in Fixed-Dimensional Continuous VASS
Michal Ajdarów, A. R. Balasubramanian, Åukasz Orlikowski
Vector Addition System with States (VASS) are a ubiquitous model of infinite-state systems consisting of a set of non-negative counters which can be incremented and decremented. It…
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…
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…
Reachability in VASS Extended with Integer Counters
Clotilde Bizière, Clotilde Bizière, Wojciech CzerwiÅski +9
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…