On the decidability of the equivalence problem for monadic recursive programs

Vladimir A. Zakharov

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2000)

  • Volume: 34, Issue: 2, page 157-171
  • ISSN: 0988-3754

How to cite

top

Zakharov, Vladimir A.. "On the decidability of the equivalence problem for monadic recursive programs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 34.2 (2000): 157-171. <http://eudml.org/doc/92628>.

@article{Zakharov2000,
author = {Zakharov, Vladimir A.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {deterministic monadic linear recursive programs},
language = {eng},
number = {2},
pages = {157-171},
publisher = {EDP-Sciences},
title = {On the decidability of the equivalence problem for monadic recursive programs},
url = {http://eudml.org/doc/92628},
volume = {34},
year = {2000},
}

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
PB - EDP-Sciences
VL - 34
IS - 2
SP - 157
EP - 171
LA - eng
KW - deterministic monadic linear recursive programs
UR - http://eudml.org/doc/92628
ER -

References

top
  1. [1] E. Ashcroft, E. Manna and A. Pnueli, A decidable properties of monadic functional schemes. J. ACM 20 (1973) 489-499. Zbl0289.68036MR400763
  2. [2] B. Courcelle, Recursive applicative program schemes, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Vol. B (1994) 459-492. Zbl0900.68095MR1127194
  3. [3] K. Culik II, New techniques for proving the decidability of equivalence problems. Lecture Notes in Comput Sci. 317 (1988) 162-175. Zbl0662.68079MR1023634
  4. [4] J. W. De Bakker and D. A. Scott, Theory of programs. Unpublished notes. Vienna: IBM Seminar (1969). 
  5. [5] E. Friedman, Equivalence problems for deterministic languages and monadic recursion schemes. J. Comput. System Sci. 14 (1977) 362-399. Zbl0358.68109MR443445
  6. [6] S. J. Garland and D. C. Luckham, Program schemes, recursion schemes and formal languages. J. Comput System Sci. 7 (1973) 119-160. Zbl0277.68010MR315930
  7. [7] E. M. Gurari and O. H. Ibarra, The complexity of equivalence problem for simple programs. J. ACM 28 (1981) 535-560. Zbl0462.68023MR624732
  8. [8] E. M. Gurari, Decidable problems for the reinforced programs. J. ACM 32 (1985) 466-483. Zbl0629.68010MR831869
  9. [9] D. Harel, Dynamic logics, in Handbook of Philosophical Logics, edited by D. Gabbay and F. Guenthner (1984) 497-604. Zbl0875.03076MR844605
  10. [10] T. Harju and J. Karhumaki, The equivalence of multi-tape finite automata. Theoret. Comput. Sci. 78 1991) 347-355. Zbl0727.68063MR1095985
  11. [11] O. H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM 25 (1978) 116-133. Zbl0365.68059MR461988
  12. [12] A. A. Letichevskii, On the equivalence of automata over semigroup. Theoretic Cybernetics 6 (1970) 3-71 (in Russian). 
  13. [13] D. C. Luckham, D. M. Park and M. S. Paterson, On formalized computer programs. J. Comput. System Sci. 4 (1970) 220-249. Zbl0209.18704MR275717
  14. [14] L. P. Lisovik, Meta-linear schemes with constant assignments. Programmirovanije, The Journal of Programming and Software Engineering (1985) 29-38 (in Russian). 
  15. [15] L. P. Lisovik, Hard sets method and semilinear reservoir method with applications. Lecture Notes in Comput. Sci. 1099 (1996) 219-231. Zbl1046.68569MR1464451
  16. [16] M. S. Paterson, Programs schemata, Machine Intelligence. Edinburgh: Univ. Press, Vol. 3 (1968) 19-31. 
  17. [17] M. S. Paterson, Decision problems in computational models. SIGPLAN Notices 7 (1972) 74-82. 
  18. [18] M. O. Rabin and D. Scott, Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-125. Zbl0158.25404MR103795
  19. [19] H. G. Rice, Classes of recurcively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 74 (1953). Zbl0053.00301MR53041
  20. [20] J. D. Rutledge, On Ianov's program schemata. J. ACM 11 (1964) 1-9. Zbl0121.12107MR166097
  21. [21] V. K. Sabelfeld, An algorithm deciding functional equivalence in a new class of program schemata. Theoret. Comput. Sci. 71 (1990) 265-279. Zbl0698.68016MR1062597
  22. [22] V. K. Sabelfeld, Tree equivalence of linear recursive schemata is polynomial-time decidable. Inform. Process. Lett. 13 (1981) 147-153. Zbl0479.68052MR651463
  23. [23] G. Senizergues, The equivalence problem for deterministic pushdown automata is decidable. Lecture Notes in Comput. Sci. 1256 (1997) 271-281. MR1616225
  24. [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. Zbl0827.68076MR1345884
  25. [25] L. G. Valiant and M. S. Paterson, Deterministic one-counter automata. J. Comput. System Sci. 10 (1975) 340-350. Zbl0307.68038MR379149
  26. [26] J. Yanov, To the equivalence and transformations of program schemata. Rep. Soviet Acad. Sci. 113 (1957) 39-42 (in Russian). Zbl0080.11502MR91539
  27. [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). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.