Reaching 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).

About joint work with Yousef Shakiba and Georg Zetzsche.

MIMUW Automata Theory Seminar
University of Warsaw, Poland
Henry Sinclair-Banks, 16/04/25