IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2024 > Reachability in Fixed VASS: Expressiveness and Lower Bounds

Andrei Draghici

Thursday, June 13, 2024

11:00am 302-Mountain View and Zoom3 (https://zoom.us/j/3911012202, password:@s3)

Andrei Draghici, PhD Student, University of Oxford

Reachability in Fixed VASS: Expressiveness and Lower Bounds

Abstract:

The recent years have seen remarkable progress in establishing the complexity of the reachability problem for vector addition systems with states (VASS), equivalently known as Petri nets. Existing work primarily considers the case in which both the VASS as well as the initial and target configurations are part of the input. In this talk, we investigate the reachability problem in the setting where the VASS and the final configuration are fixed and only the initial configuration is variable. We show that fixed VASS fully express arithmetic with counting on initial segments of the natural numbers. It follows that there is a very weak reduction from any fixed such number-theoretic predicate (e.g. square-freeness or “N1 is the number of primes smaller than N2”) to reachability in fixed VASS where configurations are presented in unary. If configurations are given in binary, we show that there is a fixed VASS with five counters whose reachability problem is PSPACE-hard.