Revisiting the Equivalence Problem for Finite Multitape Automata
Revisiting the Equivalence Problem for Finite Multitape Automata
复制标题
重新审视有限多带自动机的等价问题
DOI：
10.1007/978-3-642-39212-2_38
复制
发表时间：
2013
影响因子：
--
通讯作者：
J. Worrell
中科院分区：
文献类型：
--
作者：
J. Worrell
确定性多带自动机（或转换器）的判定等价性是一个长期存在的开放问题，直到Harju和Karhumaki在20世纪90年代初解决了这个问题。他们对可判定性的证明产生了一个co-NP上界，但显然对问题的复杂性知之甚少。在本文中，我们给出了另一种证明的可判定性，它遵循的基本策略的Harju和Karhumaki，但取代他们使用群论的结果矩阵代数。从我们的证明中，我们获得了一个简单的随机算法，用于确定确定性多带自动机以及有理数领域中具有转移权重的自动机的等价性。该算法只涉及矩阵求幂，并在多项式时间内运行每个固定数量的磁带。如果两个输入自动机是不等价的，那么算法输出一个它们不同的词。
The decidability of determining equivalence of deterministic multitape automata (or transducers) was a longstanding open problem until it was resolved by Harju and Karhumaki in the early 1990s. Their proof of decidability yields a co-NP upper bound, but apparently not much more is known about the complexity of the problem. In this paper we give an alternative proof of decidability, which follows the basic strategy of Harju and Karhumaki but replaces their use of group theory with results on matrix algebras. From our proof we obtain a simple randomised algorithm for deciding equivalence of deterministic multitape automata, as well as automata with transition weights in the field of rational numbers. The algorithm involves only matrix exponentiation and runs in polynomial time for each fixed number of tapes. If the two input automata are inequivalent then the algorithm outputs a word on which they differ.