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

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | Zbl | MR

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. | Zbl | MR

3. B. Courcelle, On Jump-Deterministic Pushdown Automata, Math. Systems Theory, Vol. 11, 1977, pp. 87-109. | Zbl | MR

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

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

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. | Zbl | MR

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

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. | Zbl | MR

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. | Zbl | MR

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. | Zbl | MR

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

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. | Zbl | MR

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

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

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. | Zbl | MR

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

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

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

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. | Zbl | MR

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. | Zbl | MR

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

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. | Zbl | MR