HDTOL matching of computations of multitape automata. (English) Zbl 0689.68103

Summary: We discuss the technique for testing the equivalence of two deterministic automata by constructing a language that matches the computations of two equivalent automata on the same input word. Specifically, we propose to use HDTOL languages that are powerful enough to match computations of many equivalent deterministic multitape automata, and at the same time, have nice decidable properties. Using this new technique of HDTOL matching, we show that the inclusion problem between an arbitrary deterministic multitape automaton and a simple one is decidable in both directions. Further, we show that the equivalence for a restricted class of transdurcers based on deterministic multitape automata is decidable.


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Berstel, J.: Transductions and Context-Free Languages. Stuttgart: Teubner 1979 · Zbl 0424.68040
[2] Bird, M.: The equivalence problem for deterministic two-tape automata. J. Comput. Syst. Sci. 7, 218-236 (1973) · Zbl 0271.94039
[3] Culik II, K., Karhumäki, J.: The equivalence of finite valued transducers (on HDTOL languages) is decidable. Theor. Comput. Sci. 47, 71-84 (1986) · Zbl 0621.68049
[4] Culik II, K., Karhumäki, J.: Loops in automata and HDTOL relations. RAIRO, Inf. Théor. Appl. (to appear) · Zbl 0701.68079
[5] Culik II, K., Salomaa, A.: On the decidability of morphic equivalence for languages. J. Comput. Syst. Sci. 17, 163-175 (1978) · Zbl 0389.68042
[6] Ginsburg, S.: The Mathematical Theory of Context-Free Languages. New York: McGraw Hill 1966 · Zbl 0184.28401
[7] Harrison, M.: Introduction to Formal Language Theory. Reading: Addison-Wesley 1978 · Zbl 0411.68058
[8] Kinber, E.: The inclusion problem for some classes of deterministic multitape automata. Theor. Comput. Sci. 26, 1-24 (1983) · Zbl 0523.68047
[9] Lewis, H.R.: A new decidability problem with applications. Proceedings of 18th FOCS Conference, pp. 62-73 (1979)
[10] Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114-125 (1959) · Zbl 0158.25404
[11] Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems. New York: Academic Press 1980 · Zbl 0508.68031
[12] Valiant, L.G.: The equivalence problem for deterministic finite-turn pushdown automata. Inf. 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.