@article{ITA_1987__21_3_245_0, author = {Courcelle, Bruno and Gallier, Jean H.}, title = {Decidable subcases of the equivalence problem for recursive program schemes}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {245--286}, publisher = {EDP-Sciences}, volume = {21}, number = {3}, year = {1987}, mrnumber = {910079}, zbl = {0634.68017}, language = {en}, url = {http://archive.numdam.org/item/ITA_1987__21_3_245_0/} }
TY - JOUR AU - Courcelle, Bruno AU - Gallier, Jean H. TI - Decidable subcases of the equivalence problem for recursive program schemes JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1987 SP - 245 EP - 286 VL - 21 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_1987__21_3_245_0/ LA - en ID - ITA_1987__21_3_245_0 ER -
%0 Journal Article %A Courcelle, Bruno %A Gallier, Jean H. %T Decidable subcases of the equivalence problem for recursive program schemes %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1987 %P 245-286 %V 21 %N 3 %I EDP-Sciences %U http://archive.numdam.org/item/ITA_1987__21_3_245_0/ %G en %F ITA_1987__21_3_245_0
Courcelle, Bruno; Gallier, Jean H. Decidable subcases of the equivalence problem for recursive program schemes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) no. 3, pp. 245-286. http://archive.numdam.org/item/ITA_1987__21_3_245_0/
1. An Improvement on Valiant's Decision Procedure for Equivalence of Deterministic Finite-Turn Pushdown Machines, Theoret. Comput. Sci., Vol. 3, 1976, pp. 305-320. | MR | Zbl
,2. Décidabilité de l'égalité des languages algébriques infinitaires simples, 3rd Symposium on Theoretical Aspects of Computer Science, L.N.C.S., Vol. 210, Springer Verlag, 1986. | MR | Zbl
,3. On Jump-Deterministic Pushdown Automata, Math. Systems Theory, Vol. 11, 1977, pp. 87-109. | MR | Zbl
,4. A Representation of Trees by Languages I, Theoret. Comput. Sci., Vol. 6, 1978, pp. 255-279. | MR | Zbl
,5. A Representation of Trees by Languages II, Theoret. Comput. Sci., Vol. 7, 1978, pp. 25-55. | MR | Zbl
,6. Completeness Results for the Equivalence of Recursive Schemes, J. Comput. System Sci., Vol. 12, (2), 1976, pp. 179-197. | MR | Zbl
and .7. Fundamental Properties of Infinite Trees, Theoret. Comput. Sci., Vol. 25, (2), 1983, pp. 95-170. | MR | Zbl
,8. IO and OI, I and II, J. Comput. System Sci., Vol. 15, (3), 1977, and Vol. 16, (1), 1978, pp. 328-353 and 67-99. | MR | Zbl
and ,9. Equivalence Problems for Deterministic Context-Free Languages and Monadic Recursion Schemes, J. Comput. System Sci., Vol. 14, 1977, pp.344-359. | MR | Zbl
,10. DPD A'S in "Atomic Normal Form" and Applications to Equivalence Problems, Theoret. Comput. Sci., Vol. 14, 1981 and Vol. 19, 1982, pp. 155-188 and 229. | Zbl
,11. Finite-Turn Pushdown Automata, S.I.A.M. J. on Control, Vol. 4, (3), 1966, pp. 429-453. | MR | Zbl
and ,12. Initial Algebra Semantics, J.A.C.M., Vol. 24, 1977, pp. 68-95. | MR | Zbl
, , and ,13. Explicit Definitions and Linguistic Dominoes, in and , Eds., Systems and Computer Science, University of Toronto Press, 1965. | MR
,14. Algebraic Semantics, L.N.C.S., Vol. 99. Springer Verlag, 1981. | MR | Zbl
,15. Introduction to Formal Language Theory, Addison Wesley, Reading, Mass, 1978. | MR | Zbl
,16. Strict Deterministic Grammars, J. Comput. System Sci., Vol. 7, 1973, pp. 237-277. | MR | Zbl
and ,17. Realtime Strict Deterministic Languages, S.I.A.M. J. on Comput., Vol. 1, 1972, pp. 333-349. | MR | Zbl
and ,18. On the Parsing of Deterministic Languages, J.A.C.M., Vol. 21, 1974, pp. 525-548. | MR | Zbl
and ,19. On the Interpretation of Recursive Polyadic Program Schemes, Symposia Mathematica, Vol. 15, Academic Press, New York, 1975, pp. 255-281. | MR | Zbl
,20. The Decidability of Equivalence for Deterministic Stateless Pushdown Automata, Information and Control, Vol. 38, 1978, pp. 367-376. | MR | Zbl
and ,21. The Equivalence Problem for Real-Time Strict Deterministic Languages, Information and Control, Vol. 45, 1980, pp. 367-376. | MR | Zbl
, and ,22. The Equivalence Problem for Two DPD A's One of which is a Finite-Turn or One-Counter Machine, J. Comput. System Sci., Vol. 23, (3), 1981, pp. 366-382. | MR | Zbl
, and ,23. The Equivalence Problem for Real-Time DPD A's, submitted for publication, 1986. | MR | Zbl
,24. Decision Procedures for Families of Deterministic Pushdown automata, Ph. D. thesis, University of Warwick, U.K., 1973.
,25. The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata, Information and Control, Vol. 25, 1975, pp. 123-133. | MR | Zbl
,