Dmitry Chistikov ; Wojciech Czerwiński ; Piotr Hofman ; Michał Pilipczuk ; Michael Wehar - Shortest paths in one-counter systems

lmcs:4037 - Logical Methods in Computer Science, March 5, 2019, Volume 15, Issue 1 - https://doi.org/10.23638/LMCS-15(1:19)2019
Shortest paths in one-counter systems

Authors: 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).


    Volume: Volume 15, Issue 1
    Published on: March 5, 2019
    Accepted on: March 5, 2019
    Submitted on: October 31, 2017
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science

    Share

    Consultation statistics

    This page has been seen 889 times.
    This article's PDF has been downloaded 261 times.