Decidable subcases of the equivalence problem for recursive program schemes
Courcelle, Bruno ; Gallier, Jean H.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987), p. 245-286 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1987-01-01
@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},
     volume = {21},
     year = {1987},
     pages = {245-286},
     mrnumber = {910079},
     zbl = {0634.68017},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 245-286. http://gdmltest.u-ga.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. | MR 443436 | Zbl 0361.68082

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 827723 | Zbl 0595.68072

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

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

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

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 411225 | Zbl 0342.68008

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

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 502290 | Zbl 0366.68053

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 443445 | Zbl 0358.68109

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 0474.68065

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 204294 | Zbl 0147.25302

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

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 237245

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

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

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

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 323164 | Zbl 0267.68034

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 356589 | Zbl 0296.68084

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

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 509559 | Zbl 0393.68078

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 582147 | Zbl 0393.68078

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 644735 | Zbl 0473.68046

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

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 391591 | Zbl 0285.68025