Shortest paths in one-counter systems

Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2

We show that any one-counter automaton with $n$ states, if its language is non-empty, accepts some word of length at most $O(n^2)$. This closes the gap between the previously known…