The Library
Shortest paths in one-counter systems
Tools
Tools
Tools
Chistikov, Dmitry, Czerwiński, Wojciech , Hofman, Piotr , Pilipczuk, Michał and Wehar, Michael (2019) Shortest paths in one-counter systems. Logical Methods in Computer Science, 15 (1). 19:1-19:28. doi:10.23638/LMCS-15(1:19)2019 ISSN 1860-5974.
|
PDF
WRAP-shortest-paths-one-counter-systems-Chistikov-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (505Kb) | Preview |
Official URL: https://doi.org/10.23638/LMCS-15(1:19)2019
Abstract
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).
| Item Type: | Journal Article | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) |
|||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Computer science | |||||||||||||||||||||
| Journal or Publication Title: | Logical Methods in Computer Science | |||||||||||||||||||||
| Publisher: | International Federation for Computational Logic | |||||||||||||||||||||
| ISSN: | 1860-5974 | |||||||||||||||||||||
| Official Date: | 5 March 2019 | |||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||
| Volume: | 15 | |||||||||||||||||||||
| Number: | 1 | |||||||||||||||||||||
| Page Range: | 19:1-19:28 | |||||||||||||||||||||
| DOI: | 10.23638/LMCS-15(1:19)2019 | |||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||||||||
| Date of first compliant deposit: | 14 March 2019 | |||||||||||||||||||||
| Date of first compliant Open Access: | 19 March 2019 | |||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
