episciences.org_4037_1624182617
1624182617
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
1860-5974
03
05
2019
Volume 15, Issue 1
Shortest paths in one-counter systems
Dmitry
Chistikov
Wojciech
Czerwiński
Piotr
Hofman
Michał
Pilipczuk
Michael
Wehar
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
03
05
2019
4037
arXiv:1510.05460
10.23638/LMCS-15(1:19)2019
https://lmcs.episciences.org/4037