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 transducers based on deterministic multitape automata is decidable.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berstel, J.: Transductions and Context-Free Languages. Stuttgart: Teubner 1979
Bird, M.: The equivalence problem for deterministic two-tape automata. J. Comput. Syst. Sci. 7, 218–236 (1973)
Culik II, K., Karhumäki, J.: The equivalence of finite valued transducers (on HDTOL languages) is decidable. Theor. Comput. Sci. 47, 71–84 (1986)
Culik II, K., Karhumäki, J.: Loops in automata and HDTOL relations. RAIRO, Inf. Théor. Appl. (to appear)
Culik II, K., Salomaa, A.: On the decidability of morphic equivalence for languages. J. Comput. Syst. Sci. 17, 163–175 (1978)
Ginsburg, S.: The Mathematical Theory of Context-Free Languages. New York: McGraw Hill 1966
Harrison, M.: Introduction to Formal Language Theory. Reading: Addison-Wesley 1978
Kinber, E.: The inclusion problem for some classes of deterministic multitape automata. Theor. Comput. Sci. 26, 1–24 (1983)
Lewis, H.R.: A new decidability problem with applications. Proceedings of 18th FOCS Conference, pp. 62–73 (1979)
Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114–125 (1959)
Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems. New York: Academic Press 1980
Valiant, L.G.: The equivalence problem for deterministic finite-turn pushdown automata. Inf. Control 25, 123–133 (1974)
Author information
Authors and Affiliations
Additional information
Reported research was supported by the National Sciences Foundation under Grant No. CCR-8702752 and by the Natural Sciences and Engineering Research Council of Canada under Grant No. A-7403
Rights and permissions
About this article
Cite this article
Culik, K., Karhumäki, J. HDTOL matching of computations of multitape automata. Acta Informatica 27, 179–191 (1989). https://doi.org/10.1007/BF00265153
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00265153