Reachability in VASS Extended with Integer Counters

Speaker(s)

Łukasz Orlikowski

Affiliation

University of Warsaw

Language of the talk

English

Date

April 29, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Reachability in VASS Extended with Integer Counters

Seminar

Seminar Automata Theory

---

I will present our recent result (with Clotilde Bizière, Wojciech Czerwiński, Roland Guttenberg, Jérôme Leroux, Vincent Michielini, Antoni Puch and Henry Sinclair-Banks) about the reachability problem in VASS Extended with Integer Counters (VASS+Z), i.e. an extension of VASS in which some counters may take negative values.

We show that reachability is NP-complete in 1-VASS+Z (i.e. when there is only one N-counter). For d ≥ 2, we prove that reachability in d-VASS+Z lies in the complexity class F_{d+2}​.

On the lower-bound side, we show that extending VASS with integer counters significantly lowers the number of N-counters needed to exhibit hardness. We prove that reachability in unary 2-VASS+Z is PSPACE-hard; without Z-counters this lower bound is only known in dimension 5. We also prove that reachability in unary 3-VASS+Z is TOWER-hard.

I plan to focus in the talk on novel techniques developed while studying reachability for this VASS extension.
 

---