Shortest Paths in One-Counter Systems
Shortest Paths in One-Counter Systems
复制标题
单柜台系统中的最短路径
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Michael Wehar
中科院分区：
文献类型：
--
作者：
D. Chistikov;Wojciech Czerwinski;Piotr Hofman;Michal Pilipczuk;Michael Wehar
我们证明，任何具有 n 个状态的单计数器自动机，如果其语言非空，则最多接受一些长度为 \(O(n^2)\) 的单词。这缩小了先前已知的 \(O(n^3)\) 上限和 \(\mathrm {\Omega}(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 \(\mathrm {\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).
准生死过程、树状 QBD、概率 1 计数器自动机和下推系统
影响因子：
2.2
作者：
Etessami K
通讯作者：
Etessami K