A class of multitape automata with a decidable equivalence problem (Q794436)

The equivalence problems for two-tape automata and multi-tape automata, each of which is contained in at most one cycle, were proved. The question of the decidability of the equivalence problem in the general case has remained open. This paper establishes the decidability of the equivalence problem for the class of multitape one-way automata admitting transitions to all except two of the tapes only a bounded number of times.