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

I will introduce a generalised reachability problem in automata with one counter with a variety of semantics. 
The goal of the presentation is to outline what features of target sets makes reachability easy or (NP-)hard.

About joint work with Yousef Shakiba and Georg Zetzsche.

Automata in the Wild 2025
University of Warwick, UK
Henry Sinclair-Banks, 01/04/25