POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

In this paper, we solve the reachability problem for branching vector addition systems (BVAS), a long-standing open problem. Our approach is based on semilinear inductive invariants. More precisely, we prove that if a configuration of a BVAS is not reachable, then there exists an inductive invariant, given as a semilinear set, that does not contain this configuration. Based on this property, we deduce a very simple (enumerative) algorithm solving the reachability problem for BVAS.