# On the Decidability of the Equivalence Problem for Monadic Recursive Programs

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

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

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