@InProceedings{Worrell:ICALP:2013,
  Author        = "Worrell, James",
  Editor        = "Fomin, Fedor V. and Freivalds, R{\={u}}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David",
  Abstract      = {The decidability of determining equivalence of deterministic multitape automata (or transducers) was a longstanding open problem until it was resolved by Harju and Karhum{\"a}ki 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 Karhum{\"a}ki 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.},
  Address       = "Berlin, Heidelberg",
  BookTitle     = "Proc. of ICALP'13",
  date-added    = "2020-10-25 12:21:05 +0100",
  date-modified = "2021-01-05 11:48:22 +0100",
  ISBN          = "978-3-642-39212-2",
  Pages         = "422--433",
  Publisher     = "Springer Berlin Heidelberg",
  Title         = "Revisiting the Equivalence Problem for Finite Multitape Automata",
  Year          = "2013",
    doi = {10.1007/978-3-642-39212-2_38},
    url = {https://doi.org/10.1007%2F978-3-642-39212-2_38},
  File          = "Revisiting the Equivalence Problem for Finite Multitape Automata - Worrell2013\_Chapter\_RevisitingTheEquivalenceProble - a - e.pdf"
}

@InProceedings{Worrell:ICALP:2013, Author = "Worrell, James", Editor = "Fomin, Fedor V. and Freivalds, R{\={u}}si{\c{n}}{\v{s}} and Kwiatkowska, Marta and Peleg, David", Abstract = {The decidability of determining equivalence of deterministic multitape automata (or transducers) was a longstanding open problem until it was resolved by Harju and Karhum{\"a}ki 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 Karhum{\"a}ki 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.}, Address = "Berlin, Heidelberg", BookTitle = "Proc. of ICALP'13", date-added = "2020-10-25 12:21:05 +0100", date-modified = "2021-01-05 11:48:22 +0100", ISBN = "978-3-642-39212-2", Pages = "422--433", Publisher = "Springer Berlin Heidelberg", Title = "Revisiting the Equivalence Problem for Finite Multitape Automata", Year = "2013", doi = {10.1007/978-3-642-39212-2_38}, url = {https://doi.org/10.1007%2F978-3-642-39212-2_38}, File = "Revisiting the Equivalence Problem for Finite Multitape Automata - Worrell2013_Chapter_RevisitingTheEquivalenceProble - a - e.pdf" }