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 upper bound of $O(n^3)$ and lower bound of $\Omega(n^2)$. More generally, we prove a tight upper bound on the length of shortest paths between arbitrary configurations in one-counter transition systems (weaker bounds have previously appeared in the literature).Comment: 28 pages, 2 figures

@article{paperbot817,
  title = {Shortest paths in one-counter systems},
  author = {Dmitry Chistikov and Wojciech Czerwiński and Piotr Hofman and Michał Pilipczuk and Michael Wehar},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 1},
  year = {2019},
  doi = {10.23638/lmcs-15(1:19)2019}
}