2013/03/26 by James Worrell, Worrell, James · 1 citation
Computer Science · #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1303.6704
openalex publication_date 2013/03/26 · arxiv created 2013/05/02 · arxiv updated 2013/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The decidability of determining equivalence of deterministic multitape automata (or transducers) was a longstanding open problem until it was resolved by Harju and Karhumäki in the early 1990s. Their proof of decidability yields a coNP 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 language equivalence of deterministic multitape automata and, more generally, multiplicity equivalence of nondeterministic multitape automata. 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.