A1 Refereed original research article in a scientific journal
THE EQUIVALENCE PROBLEM OF MULTITAPE FINITE AUTOMATA
Authors: HARJU T, KARHUMAKI J
Publisher: ELSEVIER SCIENCE BV
Publication year: 1991
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 78
Issue: 2
First page : 347
Last page: 355
Number of pages: 9
ISSN: 0304-3975
DOI: https://doi.org/10.1016/0304-3975(91)90356-7
Abstract
Using a result of B.H. Neumann we extend Eilenberg's Equality Theorem to a general result which implies that the multiplicity equivalence problem of two (nondeterministic) multitape finite automata is decidable. As a corollary we solve a long standing open problem in automata theory, namely, the equivalence problem for multitape deterministic finite automata. The main theorem states that there is a finite test set for the multiplicity equivalence of finite automata over conservative monoids embeddable in a fully ordered group.
Using a result of B.H. Neumann we extend Eilenberg's Equality Theorem to a general result which implies that the multiplicity equivalence problem of two (nondeterministic) multitape finite automata is decidable. As a corollary we solve a long standing open problem in automata theory, namely, the equivalence problem for multitape deterministic finite automata. The main theorem states that there is a finite test set for the multiplicity equivalence of finite automata over conservative monoids embeddable in a fully ordered group.
UTU Research Portal