7 papers
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…
History-Constrained Systems
Louwe B. Kuijer, David Purser, Henry Sinclair-Banks +1
We study verification problems for history-constrained systems (HCS), a model of guarded computation that uses nested systems. An outer system describes the process architecture in…
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…
A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
MichaÅ Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks
We investigate the parameterised complexity of the classic coverability problem for vector addition systems (VAS): given a finite set of vectors , an initi…
A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
Yousef Shakiba, Henry Sinclair-Banks, Georg Zetzsche
In many kinds of infinite-state systems, the coverability problem has significantly lower complexity than the reachability problem. In order to delineate the border of computationa…