{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:24:08Z","timestamp":1760081048575,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T00:00:00Z","timestamp":1551744000000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T00:00:00Z","timestamp":1551744000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T00:00:00Z","timestamp":1551744000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>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).<\/jats:p><jats:p>Comment: 28 pages, 2 figures<\/jats:p>","DOI":"10.23638\/lmcs-15(1:19)2019","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:34:51Z","timestamp":1743701691000},"source":"Crossref","is-referenced-by-count":2,"title":["Shortest paths in one-counter systems"],"prefix":"10.23638","volume":"Volume 15, Issue 1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9055-918X","authenticated-orcid":false,"given":"Dmitry","family":"Chistikov","sequence":"first","affiliation":[]},{"given":"Wojciech","family":"Czerwi\u0144ski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9866-3723","authenticated-orcid":false,"given":"Piotr","family":"Hofman","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7891-1988","authenticated-orcid":false,"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Wehar","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2019,3,5]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1510.05460v5","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1510.05460v5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:34:51Z","timestamp":1743701691000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/4037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,5]]},"references-count":0,"URL":"https:\/\/doi.org\/10.23638\/lmcs-15(1:19)2019","relation":{"has-preprint":[{"id-type":"arxiv","id":"1510.05460v4","asserted-by":"subject"},{"id-type":"arxiv","id":"1510.05460v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1510.05460","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1510.05460","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2019,3,5]]},"article-number":"4037"}}