Reachability in VASS Extended with Integer Counters

Prelegent(ci)

Łukasz Orlikowski

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

29 kwietnia 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Reachability in VASS Extended with Integer Counters

Seminarium

Seminarium „Teoria automatów”

---

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.
 

---