A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
THE EQUIVALENCE PROBLEM OF MULTITAPE FINITE AUTOMATA
Tekijät: HARJU T, KARHUMAKI J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1991
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 78
Numero: 2
Aloitussivu: 347
Lopetussivu: 355
Sivujen määrä: 9
ISSN: 0304-3975
DOI: https://doi.org/10.1016/0304-3975(91)90356-7
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali