Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-Complete
En palabras de los autores
Vector addition systems (VAS) are a fundamental model of concurrent computation in which transitions update nonnegative integer counters by adding integer vectors, provided all counters remain nonnegative. Closely related to Petri nets, VAS are the single-state counterpart of vector addition systems with states (VASS), which use finitely many states to restrict the available transitions. A classical simulation of -VASS by -VAS connects their reachability problems, but the complexity-theoretic picture of fixed-dimensional VAS remains largely unclear. While reachability in -VASS is PSPACE-complete under binary encoding, the best known upper bound for -VAS was only elementary. We prove that every reachable -VAS instance has a reachability witness of length polynomial in its unary size. Consequently, -VAS reachability is NL-complete under unary encoding and PSPACE-complete under binary encoding. We also establish a polynomial factorization of the reachability relation of every -VAS with . For -VAS, this strengthens Hopcroft and Pansiot's effective semilinearity of reachability sets to the full reachability relation. For every fixed , it also yields an upper bound for reachability in -VAS.
Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 69 pages,1 figure