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. 
@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://www.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://www.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://www.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://www.numdam.org/item/ITA_1987__21_3_245_0/

1. C. Beeri, 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. Caucal, 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. B. Courcelle, On Jump-Deterministic Pushdown Automata, Math. Systems Theory, Vol. 11, 1977, pp. 87-109. | MR | Zbl

4. B. Courcelle, A Representation of Trees by Languages I, Theoret. Comput. Sci., Vol. 6, 1978, pp. 255-279. | MR | Zbl

5. B. Courcelle, A Representation of Trees by Languages II, Theoret. Comput. Sci., Vol. 7, 1978, pp. 25-55. | MR | Zbl

6. B. Courcelle and J. Vuillemin. Completeness Results for the Equivalence of Recursive Schemes, J. Comput. System Sci., Vol. 12, (2), 1976, pp. 179-197. | MR | Zbl

7. B. Courcelle, Fundamental Properties of Infinite Trees, Theoret. Comput. Sci., Vol. 25, (2), 1983, pp. 95-170. | MR | Zbl

8. J. Engelfriet and E. Schmidt, 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

9. E. P. Friedman, Equivalence Problems for Deterministic Context-Free Languages and Monadic Recursion Schemes, J. Comput. System Sci., Vol. 14, 1977, pp.344-359. | MR | Zbl

10. J. H. Gallier, 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. S. Ginsburg and E. Spanier, Finite-Turn Pushdown Automata, S.I.A.M. J. on Control, Vol. 4, (3), 1966, pp. 429-453. | MR | Zbl

12. J. Goguen, J. Thatcher, E. Wagner and J. Wright, Initial Algebra Semantics, J.A.C.M., Vol. 24, 1977, pp. 68-95. | MR | Zbl

13. S. Gorn, Explicit Definitions and Linguistic Dominoes, in J. Hart and S. Takasu, Eds., Systems and Computer Science, University of Toronto Press, 1965. | MR

14. I. Guessarian, Algebraic Semantics, L.N.C.S., Vol. 99. Springer Verlag, 1981. | MR | Zbl

15. M. A. Harrison, Introduction to Formal Language Theory, Addison Wesley, Reading, Mass, 1978. | MR | Zbl

16. M. A. Harrison and I. M. Havel, Strict Deterministic Grammars, J. Comput. System Sci., Vol. 7, 1973, pp. 237-277. | MR | Zbl

17. M. A. Harrison and I. M. Havel, Realtime Strict Deterministic Languages, S.I.A.M. J. on Comput., Vol. 1, 1972, pp. 333-349. | MR | Zbl

18. M. A. Harrison and I. M. Havel, On the Parsing of Deterministic Languages, J.A.C.M., Vol. 21, 1974, pp. 525-548. | MR | Zbl

19. M. Nivat, On the Interpretation of Recursive Polyadic Program Schemes, Symposia Mathematica, Vol. 15, Academic Press, New York, 1975, pp. 255-281. | MR | Zbl

20. M. Oyamaguchi and N. Honda, The Decidability of Equivalence for Deterministic Stateless Pushdown Automata, Information and Control, Vol. 38, 1978, pp. 367-376. | MR | Zbl

21. M. Oyamaguchi, Y. Inagaki and N. Honda, The Equivalence Problem for Real-Time Strict Deterministic Languages, Information and Control, Vol. 45, 1980, pp. 367-376. | MR | Zbl

22. M. Oyamaguchi, Y. Inagaki and N. Honda, 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

23. M. Oyamaguchi, The Equivalence Problem for Real-Time DPD A's, submitted for publication, 1986. | MR | Zbl

24. L. G. Valiant, Decision Procedures for Families of Deterministic Pushdown automata, Ph. D. thesis, University of Warwick, U.K., 1973.

25. L. G. Valiant, The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata, Information and Control, Vol. 25, 1975, pp. 123-133. | MR | Zbl