# zbMATH — the first resource for mathematics

The equivalence problem of multitape finite automata. (English) Zbl 0727.68063
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.)

##### MSC:
 68Q45 Formal languages and automata
##### Keywords:
multitape automata; multiplicity; multiplicity equivalent
Full Text:
##### References:
  Berstei, J., Transductions and context-free languages, (1979), B.G. Teubner Stuttgart  Berstel, J.; Reutenauer, C., Rational series and their languages, (1988), Springer Berlin · Zbl 0668.68005  Bird, M., The equivalence problem for deterministic two-tape automata, J. comput. system sci., 7, 218-236, (1973) · Zbl 0271.94039  Cohn, P.M., Free rings and their relations, (1985), Academic Press New York · Zbl 0659.16001  Culik, K.; Karhumäki, J., HDT0L matching of computations of multitape automata, Acta inform., 27, 179-191, (1989) · Zbl 0689.68103  Eilenberg, S., ()  Fuchs, L., Partially ordered algebraic systems, (1963), Pergamon Press Oxford · Zbl 0137.02001  Griffiths, T.V., The unsolvability of the equivalence problem for λ-free nondeterministic generalized machines, J. ACM, 15, 409-413, (1968) · Zbl 0162.02302  Harju, T.; Karkumäki, J., Decidability of the multiplicity equivalence problem of multitape finite automata, (), 477-481  Jacobson, N., ()  Karhumäki, J., On recent trends in formal language theory, (), 136-162  Kinber, E., The inclusion problem for some classes of deterministic multitape automata, Theoret. comput. sci., 26, 1-24, (1983) · Zbl 0523.68047  Lewis, H.R., A new decidability problem with applications, (), 62-73  Neumann, B.H., On ordered division rings, Trans. amer. math. soc., 66, 202-252, (1949) · Zbl 0035.30401  Passman, D.S., The algebraic structure of group rings, (1977), Wiley New York · Zbl 0366.16003  Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. res. develop., 3, 114-125, (1959) · Zbl 0158.25404  Salomaa, A., On sentential forms of context-free grammars, Acta inform., 2, 40-49, (1973) · Zbl 0264.68029  Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, (1978), Springer-Verlag New York · Zbl 0377.68039  Valiant, L.G., The equivalence problem for deterministic finite-turn pushdown automata, Inform and control, 25, 123-133, (1974) · Zbl 0285.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.