论文标题
停止，返回和可逆的图形行动自动机的状态复杂性
State complexity of halting, returning and reversible graph-walking automata
论文作者
论文摘要
通过使用有限状态控件来决定下一步去哪里，通过在边缘的节点之间移动图形自动机（GWA）遍历图。众所周知，每个GWA都可以转换为在每个输入上停止的GWA，转变为返回初始节点以接受和可逆的GWA的GWA。本文建立了对这些转换的状态爆炸的下限，并与上限紧密匹配。结果表明，在每个输入中，在每个输入中制作$ k $ ar的图形都会停止，最多需要$ 2NK+1美元，至少$ 2（n-1）（k-3）$ state在最坏的情况下；在最坏情况下，GWA返回到初始节点之前，最多最多需要2nk+n $和至少$ 2（n-1）$ 2（n-1）（k-3）$状态；在最坏的情况下，一次满足这两个属性的自动机一次最多都有$ 4NK+1 $和至少$ 4（n-1）（k-3）$状态。在最坏的情况下，可逆的自动机最多具有$ 4NK+1 $和至少$ 4（n-1）（K-3）-1 $状态。
Graph-walking automata (GWA) traverse graphs by moving between the nodes following the edges, using a finite-state control to decide where to go next. It is known that every GWA can be transformed to a GWA that halts on every input, to a GWA returning to the initial node in order to accept, and to a reversible GWA. This paper establishes lower bounds on the state blow-up of these transformations, as well as closely matching upper bounds. It is shown that making an $n$-state GWA traversing $k$-ary graphs halt on every input requires at most $2nk+1$ states and at least $2(n-1)(k-3)$ states in the worst case; making a GWA return to the initial node before acceptance takes at most $2nk+n$ and at least $2(n-1)(k-3)$ states in the worst case; Automata satisfying both properties at once have at most $4nk+1$ and at least $4(n-1)(k-3)$ states in the worst case. Reversible automata have at most $4nk+1$ and at least $4(n-1)(k-3)-1$ states in the worst case.
