10.23638/LMCS-15(1:19)2019
Chistikov, Dmitry
Dmitry
Chistikov
Czerwiński, Wojciech
Wojciech
Czerwiński
Hofman, Piotr
Piotr
Hofman
Pilipczuk, Michał
Michał
Pilipczuk
Wehar, Michael
Michael
Wehar
Shortest paths in one-counter systems
episciences.org
2019
Computer Science - Formal Languages and Automata Theory
Computer Science - Logic in Computer Science
contact@episciences.org
episciences.org
2017-10-31T16:36:13+01:00
2019-04-18T16:29:54+02:00
2019-03-05
eng
Journal article
https://lmcs.episciences.org/4037
arXiv:1510.05460
1860-5974
PDF
1
Logical Methods in Computer Science ; Volume 15, Issue 1 ; 1860-5974
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