A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One

Stefan Göller, Christoph Haase, Ranko Lazic, Patrick Totzke

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.

A sequence of transitions in a one-dimensional VASS.

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.

The expansion of a partial reachability tree.

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

Abstract

Branching VASS (BVASS) generalise vector addition systems with states by allowing for special branching transitions that can non-deterministically distribute a counter value between two control states. A run of a BVASS consequently becomes a tree, and reachability is to decide whether a given configuration is the root of a reachability tree. This paper shows P-completeness of reachability in BVASS in dimension one, the first decidability result for reachability in a subclass of BVASS known so far. Moreover, we show that coverability and boundedness in BVASS in dimension one are P-complete as well.
BibTeX
@inproceedings{goller2016polynomial,
  author = {Stefan Göller and Christoph Haase and Ranko Lazic and Patrick Totzke},
  title = {{A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One}},
  booktitle = {ICALP},
  year = {2016},
  url = {https://openreview.net/forum?id=PB57l8rqKZz},
}
Figure