Loops in automata and HDTOL relations. (English) Zbl 0701.68079

Summary: We show that n-tape automata containing only simple loops, i.e. no state is involved in two loops, have several properties which general n-tape automata, or even automata with parallel loops only, do not have. The intersection of relations defined by two simple n-tape automata is so called HDTOL relation. This implies several old and new decidability results for simple n-tape automata.


68Q45 Formal languages and automata
Full Text: DOI EuDML


[1] J. BERSTEL, Transductions and Context-Free Languages, Teubner, Stuttgart, 1979. Zbl0424.68040 MR549481 · Zbl 0424.68040
[2] M. BIRD, The Equivalence Problem for Deterministic two-tape Automata, J. Comput. Sci., Vol. 7, 1973, pp.218-236. Zbl0271.94039 MR342290 · Zbl 0271.94039
[3] K. CULIK II, A Purely Homomorphic Characterization of Recursively Enumerate Sets, J. Assoc. Comput. Mach., Vol. 6, 1979, pp.345-350. Zbl0395.68076 MR528036 · Zbl 0395.68076
[4] K. CULIK II and J. KARHUMÄKI, Systems of equations over a free Monoid and Ehrenfeucht’s Conjecture, Discrete Math., Vol. 43, 1983, pp. 139-153. Zbl0528.68057 MR685623 · Zbl 0528.68057
[5] K. CULIK II and J. KARHUMÄKI, The Equivalence of Finite Valued Ttansducers (on HDTOL Languages) is Decidable, Theoret. Comput. Sci., Vol. 47, 1986, pp. 71-84. Zbl0621.68049 MR871465 · Zbl 0621.68049
[6] K. CULIK II and J. KARHUMÄKI, Systems of Equations Over a Finitely Generated free Monoid Having an Effectively Equivalent Finite Subsystem, Lecture Notes in Mathematics (to appear). Zbl0648.68084 · Zbl 0648.68084
[7] K. CULIK II and J. KARHUMÄKI, HDTOL Matching of Computations of Multiple Automata, Acta Informatica (to appear). Zbl0689.68103 · Zbl 0689.68103
[8] S. GINSBURG, The Matematical Theory of Context-Free Languages, McGraw Hill, New York, 1966. Zbl0184.28401 MR211815 · Zbl 0184.28401
[9] S. GINSBURG and E. H. SPANIER, AFL with the Semilinear Property, J of Comput. and System Sciences, Vol. 5, 1971, pp. 365-396. Zbl0235.68029 MR339558 · Zbl 0235.68029
[10] M. HARRISON, Introduction to Formal Langage Theory, Addison-Wesley, Reading, 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058
[11] E. KINBER, The Inclusion Problem for Some Classes of Deterministic Multitape Automata, Theoret. Comput. Sci., Vol. 26, 1983, pp. 1-24. Zbl0523.68047 MR726910 · Zbl 0523.68047
[12] M. LATTEAUX, Intersections de languages algébriques bornés Acta Informatica, Vol., 11, 1979, pp. 233-240. Zbl0416.68064 MR525751 · Zbl 0416.68064
[13] H. R. LEWIS, A New Decidability Problem with Applications, Proceedings of 18th FOCS Conference, 1979, pp. 62-73. MR488960
[14] M. RABIN and D. SCOTT, Finite Automata and their Decision Problems, I.B.M. J. Res. Develop., Vol. 3, 1959, pp. 114-125. Zbl0158.25404 MR103795 · Zbl 0158.25404
[15] G. ROZENBERG and A. SALOMAA, The Mathematical Theory of L Systems, Academic Press, New York, 1980. Zbl0508.68031 MR561711 · Zbl 0508.68031
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.