Reaching Semilinear Target Sets in Automata with One Counter

Speaker(s)

Henry Sinclair-Banks

Affiliation

University of Warsaw

Language of the talk

English

Date

April 16, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Reaching Semilinear Target Sets in Automata with One Counter

Seminar

Seminar Automata Theory

---

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

---