一句话：证明 n 状态一计数器自动机非空语言存在 O(n^2) 长度接受词，并给出配置间最短路径的紧上界。
论文研究一计数器自动机与一计数器迁移系统中的最短路径长度。作者证明：任意具有 n 个状态的一计数器自动机，只要其语言非空，就存在长度不超过 O(n^2) 的接受词。该结果将此前 O(n^3) 的上界与 Ω(n^2) 的下界之间的差距完全闭合。进一步，作者将结论推广到一计数器迁移系统中任意两个配置之间的最短路径，证明其长度具有紧上界；此前文献中只给出较弱的界。论文属于自动机与形式语言理论中的复杂度与可判定性研究，主要贡献是精确刻画最短路径的最坏情况长度。
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
@article{paperbot817,
title = {Shortest paths in one-counter systems},
author = {Dmitry Chistikov and Wojciech Czerwiński and Piotr Hofman and Michał Pilipczuk and Michael Wehar},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 1},
year = {2019},
doi = {10.23638/lmcs-15(1:19)2019}
}