Which Semilinear Target Sets Make Reachability in 1-VASS Easy?

I will introduce a generalised reachability problem in automata with one counter that is interesting for a variety of semantics.
In this presentation, I will focus on 1-VASS and the goal is to outline what features of semilinear target sets make reachability easy or (NP-)hard. 
I will also briefly touch on a new AC¹ algorithm for coverability in binary-encoded 1-VASS (which improves over the previous NC² algorithm of Almagor, Cohen, Pérez, Shirmohammadi, and Worrell) that has a simple and rather pleasing combinatorial description. 

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

Highlights 2025
University of Saarland, Saarbrücken, Germany
Henry Sinclair-Banks, 03/09/25