On the Decidability of the Equivalence Problem for Monadic Recursive Programs

Vladimir A. Zakharov

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

top
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.

How to cite

top

Zakharov, Vladimir A.. "On the Decidability of the Equivalence Problem for Monadic Recursive Programs." RAIRO - Theoretical Informatics and Applications 34.2 (2010): 157-171. <http://eudml.org/doc/222080>.

@article{Zakharov2010,
abstract = { 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. },
author = {Zakharov, Vladimir A.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Recursive program; equivalence problem; decidability; monoid.; deterministic monadic linear recursive programs},
language = {eng},
month = {3},
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/222080},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Zakharov, Vladimir A.
TI - On the Decidability of the Equivalence Problem for Monadic Recursive Programs
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 2
SP - 157
EP - 171
AB - 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.
LA - eng
KW - Recursive program; equivalence problem; decidability; monoid.; deterministic monadic linear recursive programs
UR - http://eudml.org/doc/222080
ER -

References

top
  1. E. Ashcroft, E. Manna and A. Pnueli, A decidable properties of monadic functional schemes. J. ACM20 (1973) 489-499.  Zbl0289.68036
  2. B. Courcelle, Recursive applicative program schemes, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Vol. B (1994) 459-492.  Zbl0900.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
  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.  
  6. S.J. Garland and D.C. Luckham, Program schemes, recursion schemes and formal languages. J. Comput. System Sci.7 (1973) 119-160.  Zbl0277.68010
  7. E.M. Gurari and O.H. Ibarra, The complexity of equivalence problem for simple programs. J. ACM28 (1981) 535-560.  Zbl0462.68023
  8. E.M. Gurari, Decidable problems for the reinforced programs. J. ACM32 (1985) 466-483.  Zbl0629.68010
  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.  Zbl0727.68063
  11. O.H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM25 (1978) 116-133.  Zbl0365.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.  Zbl0209.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.  Zbl1046.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
  19. H.G. Rice, Classes of recurcively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 74 (1953).  Zbl0053.00301
  20. J.D. Rutledge, On Ianov's program schemata. J. ACM11 (1964) 1-9.  Zbl0121.12107
  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
  22. V.K. Sabelfeld, Tree equivalence of linear recursive schemata is polynomial-time decidable. Inform. Process. Lett.13 (1981) 147-153.  Zbl0479.68052
  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.  Zbl0827.68076
  25. L.G. Valiant and M.S. Paterson, Deterministic one-counter automata. J. Comput. System Sci. 10 (1975) 340-350.  Zbl0307.68038
  26. J. Yanov, To the equivalence and transformations of program schemata. Rep. Soviet Acad. Sci. 113 (1957) 39-42 (in Russian).  Zbl0080.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).  

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.