A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter.

I will introduce a (novel) generalised reachability problem in automata with one counter with a variety of semantics. The goal of the seminar is to identify what features of target sets make the reachability problem easy or (NP-)hard and to detail some new concepts and algorithmic techniques for one-dimensional integer VASS (and 1-dimensional Parikh automata).

Based on joint work with Yousef Shakiba and Georg Zetzsche that has been accepted to LICS’25.

BASICS Ground Seminar
Shanghai Jiao Tong University, Shanghai, China
Henry Sinclair-Banks, 18/06/25