The equivalence problem of multitape finite automata (Q804302)

In 1959 Rabin and Scott introduced the notion of a multitape finite automaton. Since then several attempts have been made to solve the decidability of the equivalence between two deterministic automata of this type, but only partial results have been obtained. For instance, the two-tape case was solved by M. Bird in 1973. It should be noticed that the inclusion problem does not help, because it is easily shown to be undecidable by means of Post Correspondence Problem. Instead of deterministic multitape automata the authors of the paper under review consider nondeterministic multitape automata with multiplicities. Thus they ask, whether two given automata are multiplicitly equivalent, i.e., whether they accept the same n-tuples of words exactly the same number of times. If this problem is decidable, then the equivalence between two deterministic or, more generally, unambiguous multitape automata, is so. The authors reduce the multiplicity equivalence problem to the corresponding problem for one-tape automata in which the multiplicities are taken from a polynomial semiring. The technique used is that of formal power series. More precisely, given a multitape automaton, a formal power series over a one-letter alphabet \(\{\) \(a\}\) is constructed such that, for all n, the coefficient of the word \(a^ n\) reveals the multiplicities of all inputs of length n. Consequently, two multitape automata are multiplicity equivalent if and only if the difference of the corresponding series is zero. Simple arguments based on linear algebra show that if a formal power series r is R-rational (equivalently, R-recognizable, for free monoids) and R is a semiring that can be embedded in a division ring, then \(r=0\) holds if and only if the coefficients of all words whose length is less than the size of a matrix representation of r are equal to zero. Thus one gets a finite test set provided R satisfies the condition. Now, R is the polynomial semiring N(M) where all coefficients are nonnegative integers and M is the direct product of finitely many free monoids. Using results from classical algebra it can be proved that R can be embedded in a division ring. Consequently, the multiplicity equivalence problem for finite multitape automata is decidable, and a generalization of an old problem has been settled. (As a matter of fact, it is proved more generally that there exists a finite test set for the multiplicity equivalence of finite automata over conservative monoids embeddable in a fully ordered group.)