×

On the decidability of the equivalence problem for monadic recursive programs. (English) Zbl 0962.68091

Summary: We present a uniform and easy-to-use technique for deciding the equivalence problem for deterministic monadic linear recursive programs. The key idea is to reduce this problem to the well-known group-theoretic problems by revealing an algebraic nature of program computations. We show that the equivalence problem for monadic linear recursive programs over finite and fixed alphabets of basic functions and logical conditions is decidable in polynomial time for the semantics based on the free monoids and free commutative monoids.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[1] E. Ashcroft, E. Manna and A. Pnueli, A decidable properties of monadic functional schemes. J. ACM20 (1973) 489-499. · Zbl 0289.68036 · doi:10.1145/321765.321780
[2] B. Courcelle, Recursive applicative program schemes, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Vol. B (1994) 459-492. · Zbl 0900.68095
[3] K. Culik II, New techniques for proving the decidability of equivalence problems. Lecture Notes in Comput. Sci.317 (1988) 162-175. Zbl0662.68079 · Zbl 0662.68079
[4] J.W. De Bakker and D.A. Scott, Theory of programs. Unpublished notes. Vienna: IBM Seminar (1969).
[5] E. Friedman, Equivalence problems for deterministic languages and monadic recursion schemes. J. Comput. System Sci.14 (1977) 362-399. Zbl0358.68109 · Zbl 0358.68109 · doi:10.1016/S0022-0000(77)80019-6
[6] S.J. Garland and D.C. Luckham, Program schemes, recursion schemes and formal languages. J. Comput. System Sci.7 (1973) 119-160. · Zbl 0277.68010 · doi:10.1016/S0022-0000(73)80040-6
[7] E.M. Gurari and O.H. Ibarra, The complexity of equivalence problem for simple programs. J. ACM28 (1981) 535-560. · Zbl 0462.68023 · doi:10.1145/322261.322270
[8] E.M. Gurari, Decidable problems for the reinforced programs. J. ACM32 (1985) 466-483. · Zbl 0629.68010 · doi:10.1145/3149.3157
[9] D. Harel, Dynamic logics, in Handbook of Philosophical Logics, edited by D. Gabbay and F. Guenthner (1984) 497-604.
[10] T. Harju and J. Karhumaki, The equivalence of multi-tape finite automata. Theoret. Comput. Sci.78 (1991) 347-355. · Zbl 0727.68063 · doi:10.1016/0304-3975(91)90356-7
[11] O.H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM25 (1978) 116-133. · Zbl 0365.68059 · doi:10.1145/322047.322058
[12] A.A. Letichevskii, On the equivalence of automata over semigroup. Theoretic Cybernetics 6 (1970) 3-71 (in Russian).
[13] D.C. Luckham, D.M. Park and M.S. Paterson, On formalized computer programs. J. Comput. System Sci.4 (1970) 220-249. · Zbl 0209.18704 · doi:10.1016/S0022-0000(70)80022-8
[14] L.P. Lisovik, Meta-linear schemes with constant assignments. Programmirovanije, The Journal of Programming and Software Engineering (1985) 29-38 (in Russian).
[15] L.P. Lisovik, Hard sets method and semilinear reservoir method with applications. Lecture Notes in Comput. Sci.1099 (1996) 219-231. · Zbl 1046.68569
[16] M.S. Paterson, Programs schemata, Machine Intelligence. Edinburgh: Univ. Press, Vol. 3 (1968) 19-31.
[17] M.S. Paterson, Decision problems in computational models. SIGPLAN Notices7 (1972) 74-82.
[18] M.O. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop.3 (1959) 114-125. Zbl0158.25404 · Zbl 0158.25404
[19] H.G. Rice, Classes of recurcively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 74 (1953). Zbl0053.00301 · Zbl 0053.00301 · doi:10.2307/1990888
[20] J.D. Rutledge, On Ianov’s program schemata. J. ACM11 (1964) 1-9. · Zbl 0121.12107 · doi:10.1145/321203.321204
[21] V.K. Sabelfeld, An algorithm deciding functional equivalence in a new class of program schemata. Theoret. Comput. Sci.71 (1990) 265-279. Zbl0698.68016 · Zbl 0698.68016 · doi:10.1016/0304-3975(90)90201-R
[22] V.K. Sabelfeld, Tree equivalence of linear recursive schemata is polynomial-time decidable. Inform. Process. Lett.13 (1981) 147-153. Zbl0479.68052 · Zbl 0479.68052 · doi:10.1016/0020-0190(81)90046-6
[23] G. Senizergues, The equivalence problem for deterministic pushdown automata is decidable. Lecture Notes in Comput. Sci.1256 (1997) 271-281.
[24] E. Tomita and K. Seino, The extended equivalence problem for a class of non-real-time deterministic pushdown automata. Acta Informatica32 (1995) 395-413. · Zbl 0827.68076 · doi:10.1007/BF01178385
[25] L.G. Valiant and M.S. Paterson, Deterministic one-counter automata. J. Comput. System Sci. 10 (1975) 340-350. · Zbl 0307.68038 · doi:10.1016/S0022-0000(75)80005-5
[26] J. Yanov, To the equivalence and transformations of program schemata. Rep. Soviet Acad. Sci. 113 (1957) 39-42 (in Russian). Zbl0080.11502 · Zbl 0080.11502
[27] V.A. Zakharov, The equivalence of monadic linear functional programs is decidable in polynomial time, in Proc. of the 2nd Conf. on Discrete Models in Control System Theory (1997) 35-39 (in Russian).
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.