On the decidability of the equivalence problem for monadic recursive programs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 2, pp. 157-171. 
@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},
     pages = {157--171},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {2},
     year = {2000},
     mrnumber = {1774307},
     zbl = {0962.68091},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2000__34_2_157_0/}
}
TY  - JOUR
AU  - Zakharov, Vladimir A.
TI  - On the decidability of the equivalence problem for monadic recursive programs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 157
EP  - 171
VL  - 34
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2000__34_2_157_0/
LA  - en
ID  - ITA_2000__34_2_157_0
ER  - 
%0 Journal Article
%A Zakharov, Vladimir A.
%T On the decidability of the equivalence problem for monadic recursive programs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 157-171
%V 34
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2000__34_2_157_0/
%G en
%F 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) no. 2, pp. 157-171. http://archive.numdam.org/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 | Zbl

[2] B. Courcelle, Recursive applicative program schemes, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Vol. B (1994) 459-492. | MR | Zbl

[3] K. Culik Ii, New techniques for proving the decidability of equivalence problems. Lecture Notes in Comput Sci. 317 (1988) 162-175. | MR | Zbl

[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 | Zbl

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

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

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

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

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

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

[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 | Zbl

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

[26] J. Yanov, To the equivalence and transformations of program schemata. Rep. Soviet Acad. Sci. 113 (1957) 39-42 (in Russian). | MR | Zbl

[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).