{"docId":5251,"paperId":4037,"url":"https:\/\/lmcs.episciences.org\/4037","doi":"10.23638\/LMCS-15(1:19)2019","journalName":"Logical Methods in Computer Science","issn":"","eissn":"1860-5974","volume":[{"vid":356,"name":"Volume 15, Issue 1"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"1510.05460","repositoryVersion":5,"repositoryLink":"https:\/\/arxiv.org\/abs\/1510.05460v5","dateSubmitted":"2017-10-31 16:36:13","dateAccepted":"2019-03-05 20:48:44","datePublished":"2019-03-05 20:51:35","titles":["Shortest paths in one-counter systems"],"authors":["Chistikov, Dmitry","Czerwi\u0144ski, Wojciech","Hofman, Piotr","Pilipczuk, Micha\u0142","Wehar, Michael"],"abstracts":["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"],"keywords":["Computer Science - Formal Languages and Automata Theory","Computer Science - Logic in Computer Science"]}