Abstract
Branching Vector Addition Systems with States (BVASS) extend the standard VASS model by allowing transitions to split a counter value between two new states. While reachability in standard VASS is known to be decidable with a non-primitive recursive upper bound, the complexity of BVASS reachability remains a major open problem. This paper demonstrates that for the one-dimensional case (BVASS1), reachability, coverability, and boundedness are not only decidable but are P-complete. This result is achieved through a polynomial-time algorithm based on modular certificates and expandable partial reachability trees.
Introduction
Vector Addition Systems with States (VASS), or Petri nets, are a cornerstone of concurrent systems modeling. They consist of a finite-state controller managing several non-negative integer counters. Branching VASS (BVASS) introduces a branching mechanism: a single state can split its current counter value across two successor states. For instance, a state with a counter value of 10 might branch into two states with values 4 and 6.
In general dimensions, the decidability of BVASS reachability is unknown, and it is equivalent to the decidability of the multiplicative-exponential fragment of linear logic. Even in one dimension (BVASS1), the problem is non-trivial because branching can generate reachability trees of exponential size relative to the input, seemingly precluding polynomial-time solutions.
The One-Dimensional Challenge
The primary difficulty in BVASS1 is the "Small-Model" Paradox. Even if a target configuration is reachable, the smallest tree witnessing this reachability might contain an exponential number of nodes. A naive search through these trees would lead to exponential time complexity.
Standard 1D VASS reachability (without branching) is PSPACE-complete. Surprisingly, the addition of branching in one dimension actually allows for a more structured decomposition of the problem, leading to a lower complexity class: P-complete.
Methodology: Modular Certificates and Expandable Trees
The authors overcome the exponential witness problem by developing a "certificate" system that can be verified in polynomial time. Their approach rests on three pillars:
1. Residue Reachability
The algorithm abstracts away specific large counter values by focusing on modular arithmetic. It determines if a state is reachable with a counter value $n$ that satisfies a specific condition: $n \equiv r \pmod d$. This "residue reachability" can be computed efficiently, allowing the algorithm to handle large values without explicitly representing them.
2. Expandable Partial Reachability Trees
Instead of constructing a full, potentially exponential reachability tree, the algorithm searches for "expandable" trees. These are smaller structures where specific leaf nodes can be "pumped" or repeated to reach arbitrarily high counter values within certain residue classes.
3. Alternating Logspace Procedure
The search for these certificates is formalized as an alternating logspace procedure. In computational complexity theory, the class ALogSpace is equivalent to P (Polynomial Time). By showing that the existence of an expandable tree can be checked in alternating logspace, the authors prove the existence of a polynomial-time algorithm.
Key Results
The paper establishes that reachability, coverability, and boundedness in BVASS1 are P-complete. This is the first decidability result for any reachability subclass of BVASS. The P-completeness is particularly notable because it places a problem often considered "monstrous" into a surprisingly efficient complexity class.
Discussion and Future Work
The techniques developed here—specifically the modular pumping lemmas—are highly tailored to the one-dimensional case. Generalizing these results to higher dimensions (BVASS2, BVASS3, etc.) remains a significant challenge, as the 1D modular arithmetic doesn't directly translate to multi-dimensional vector spaces.
However, settling the 1D case provides a roadmap and renewed optimism for the general BVASS reachability problem. It demonstrates that even when witness structures are exponentially large, clever abstractions like modular certificates can yield efficient decision procedures.
Summary updated