THE EQUIVALENCE PROBLEM OF MULTITAPE FINITE AUTOMATA



: HARJU T, KARHUMAKI J

Publisher: ELSEVIER SCIENCE BV

: 1991

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 78

: 2

: 347

: 355

: 9

: 0304-3975

DOI: https://doi.org/10.1016/0304-3975(91)90356-7


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.



Last updated on 2025-13-10 at 11:25