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.)

68Q45 Formal languages and automata
Full Text: DOI
[1] Berstei, J., Transductions and context-free languages, (1979), B.G. Teubner Stuttgart
[2] Berstel, J.; Reutenauer, C., Rational series and their languages, (1988), Springer Berlin · Zbl 0668.68005
[3] Bird, M., The equivalence problem for deterministic two-tape automata, J. comput. system sci., 7, 218-236, (1973) · Zbl 0271.94039
[4] Cohn, P.M., Free rings and their relations, (1985), Academic Press New York · Zbl 0659.16001
[5] Culik, K.; Karhumäki, J., HDT0L matching of computations of multitape automata, Acta inform., 27, 179-191, (1989) · Zbl 0689.68103
[6] Eilenberg, S., ()
[7] Fuchs, L., Partially ordered algebraic systems, (1963), Pergamon Press Oxford · Zbl 0137.02001
[8] Griffiths, T.V., The unsolvability of the equivalence problem for λ-free nondeterministic generalized machines, J. ACM, 15, 409-413, (1968) · Zbl 0162.02302
[9] Harju, T.; Karkumäki, J., Decidability of the multiplicity equivalence problem of multitape finite automata, (), 477-481
[10] Jacobson, N., ()
[11] Karhumäki, J., On recent trends in formal language theory, (), 136-162
[12] Kinber, E., The inclusion problem for some classes of deterministic multitape automata, Theoret. comput. sci., 26, 1-24, (1983) · Zbl 0523.68047
[13] Lewis, H.R., A new decidability problem with applications, (), 62-73
[14] Neumann, B.H., On ordered division rings, Trans. amer. math. soc., 66, 202-252, (1949) · Zbl 0035.30401
[15] Passman, D.S., The algebraic structure of group rings, (1977), Wiley New York · Zbl 0366.16003
[16] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. res. develop., 3, 114-125, (1959) · Zbl 0158.25404
[17] Salomaa, A., On sentential forms of context-free grammars, Acta inform., 2, 40-49, (1973) · Zbl 0264.68029
[18] Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, (1978), Springer-Verlag New York · Zbl 0377.68039
[19] 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.