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.  
  2. B. Courcelle, Recursive applicative program schemes, in Handbook of Theoretical Computer Science, edited by J. van Leeuwen, Vol. B (1994) 459-492.  
  3. K. Culik II, New techniques for proving the decidability of equivalence problems. Lecture Notes in Comput. Sci.317 (1988) 162-175.  
  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.  
  7. E.M. Gurari and O.H. Ibarra, The complexity of equivalence problem for simple programs. J. ACM28 (1981) 535-560.  
  8. E.M. Gurari, Decidable problems for the reinforced programs. J. ACM32 (1985) 466-483.  
  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.  
  11. O.H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM25 (1978) 116-133.  
  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.  
  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.  
  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.  
  19. H.G. Rice, Classes of recurcively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 74 (1953).  
  20. J.D. Rutledge, On Ianov's program schemata. J. ACM11 (1964) 1-9.  
  21. V.K. Sabelfeld, An algorithm deciding functional equivalence in a new class of program schemata. Theoret. Comput. Sci.71 (1990) 265-279.  
  22. V.K. Sabelfeld, Tree equivalence of linear recursive schemata is polynomial-time decidable. Inform. Process. Lett.13 (1981) 147-153.  
  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.  
  25. L.G. Valiant and M.S. Paterson, Deterministic one-counter automata. J. Comput. System Sci. 10 (1975) 340-350.  
  26. J. Yanov, To the equivalence and transformations of program schemata. Rep. Soviet Acad. Sci. 113 (1957) 39-42 (in Russian).  
  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.