On the decidability of the equivalence problem for monadic recursive programs
Zakharov, Vladimir A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 157-171 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_2_157_0,
     author = {Zakharov, Vladimir A.},
     title = {On the decidability of the equivalence problem for monadic recursive programs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {157-171},
     mrnumber = {1774307},
     zbl = {0962.68091},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_2_157_0}
}

Zakharov, Vladimir A. On the decidability of the equivalence problem for monadic recursive programs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 157-171. http://gdmltest.u-ga.fr/item/ITA_2000__34_2_157_0/

[1] E. Ashcroft, E. Manna and A. Pnueli, A decidable properties of monadic functional schemes. J. ACM 20 (1973) 489-499. | MR 400763 | Zbl 0289.68036

[2] B. Courcelle, Recursive applicative program schemes, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Vol. B (1994) 459-492. | MR 1127194 | 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. | MR 1023634 | 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. | MR 443445 | Zbl 0358.68109

[6] S. J. Garland and D. C. Luckham, Program schemes, recursion schemes and formal languages. J. Comput System Sci. 7 (1973) 119-160. | MR 315930 | Zbl 0277.68010

[7] E. M. Gurari and O. H. Ibarra, The complexity of equivalence problem for simple programs. J. ACM 28 (1981) 535-560. | MR 624732 | Zbl 0462.68023

[8] E. M. Gurari, Decidable problems for the reinforced programs. J. ACM 32 (1985) 466-483. | MR 831869 | Zbl 0629.68010

[9] D. Harel, Dynamic logics, in Handbook of Philosophical Logics, edited by D. Gabbay and F. Guenthner (1984) 497-604. | MR 844605 | Zbl 0875.03076

[10] T. Harju and J. Karhumaki, The equivalence of multi-tape finite automata. Theoret. Comput. Sci. 78 1991) 347-355. | MR 1095985 | Zbl 0727.68063

[11] O. H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM 25 (1978) 116-133. | MR 461988 | Zbl 0365.68059

[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. | MR 275717 | Zbl 0209.18704

[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. | MR 1464451 | 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 Notices 7 (1972) 74-82.

[18] M. O. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-125. | MR 103795 | Zbl 0158.25404

[19] H. G. Rice, Classes of recurcively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 74 (1953). | MR 53041 | Zbl 0053.00301

[20] J. D. Rutledge, On Ianov's program schemata. J. ACM 11 (1964) 1-9. | MR 166097 | Zbl 0121.12107

[21] V. K. Sabelfeld, An algorithm deciding functional equivalence in a new class of program schemata. Theoret. Comput. Sci. 71 (1990) 265-279. | MR 1062597 | Zbl 0698.68016

[22] V. K. Sabelfeld, Tree equivalence of linear recursive schemata is polynomial-time decidable. Inform. Process. Lett. 13 (1981) 147-153. | MR 651463 | Zbl 0479.68052

[23] G. Senizergues, The equivalence problem for deterministic pushdown automata is decidable. Lecture Notes in Comput. Sci. 1256 (1997) 271-281. | MR 1616225

[24] E. Tomita and K. Seino, The extended equivalence problem for a class of non-real-time deterministic pushdown automata. Acta Informatica 32 (1995) 395-413. | MR 1345884 | Zbl 0827.68076

[25] L. G. Valiant and M. S. Paterson, Deterministic one-counter automata. J. Comput. System Sci. 10 (1975) 340-350. | MR 379149 | Zbl 0307.68038

[26] J. Yanov, To the equivalence and transformations of program schemata. Rep. Soviet Acad. Sci. 113 (1957) 39-42 (in Russian). | MR 91539 | 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).