We show that any one-counter automaton with n states, if its language is
non-empty, accepts some word of length at most O(n2). This closes the gap
between the previously known upper bound of O(n3) and lower bound of
Ω(n2). 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).
Ekaterina Shemetova;Alexander Okhotin;Semyon Grigorev, Lecture notes in computer science, Rational Index of Languages with Bounded Dimension of Parse Trees, pp. 263-273, 2022, 10.1007/978-3-031-05578-2_21.