Reachability in Fixed Dimension Vector Addition Systems with States

The reachability problem is a central decision problem in verification of vector addition systems with states (VASS), which are equivalent to Petri nets and form one of the most studied and applied models of concurrency. Reachability for VASS is also inter-reducible with a plethora of problems from a number of areas of computer science. In spite of recent progress, the complexity of the reachability problem remains unsettled, and it is closely related to the lengths of shortest VASS runs that witness reachability. We discuss three recent results for VASS of fixed dimension. For the first two, we assume that the integers in the input are given in unary, and that the control graph of the given VASS is flat (i. e. , without nested cycles). We construct a family of VASS in dimension 3 whose shortest runs are exponential, and we show that the reachability problem is NP-hard in dimension 7. These results resolve negatively questions that had been posed by the works of Blondin et al. in LICS 2015 and Englert et al. in LICS 2016, and contribute a first construction that distinguishes -dimensional flat VASS from 2-dimensional ones. The third result, by means of a novel family of products of integer fractions, shows that 4-dimensional VASS can have doubly exponentially long shortest runs. The smallest dimension for which this was previously known is 14. The discussed results have been obtained in a joint work with Wojciech Czerwinski, Ranko Lazic, Jerome Leroux and Filip Mazowiecki.

Authors

• Sławomir Lasota

Keywords

No keywords are indexed for this paper.