Decidable subcases of the equivalence problem for recursive program schemes

Bruno Courcelle; Jean H. Gallier

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1987)

  • Volume: 21, Issue: 3, page 245-286
  • ISSN: 0988-3754

How to cite

top

Courcelle, Bruno, and Gallier, Jean H.. "Decidable subcases of the equivalence problem for recursive program schemes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 21.3 (1987): 245-286. <http://eudml.org/doc/92287>.

@article{Courcelle1987,
author = {Courcelle, Bruno, Gallier, Jean H.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {program schemes; equivalence problem; polyadic recursive schemes; deterministic push-down automata; decidability},
language = {eng},
number = {3},
pages = {245-286},
publisher = {EDP-Sciences},
title = {Decidable subcases of the equivalence problem for recursive program schemes},
url = {http://eudml.org/doc/92287},
volume = {21},
year = {1987},
}

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
PB - EDP-Sciences
VL - 21
IS - 3
SP - 245
EP - 286
LA - eng
KW - program schemes; equivalence problem; polyadic recursive schemes; deterministic push-down automata; decidability
UR - http://eudml.org/doc/92287
ER -

References

top
  1. 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. Zbl0361.68082MR443436
  2. 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. Zbl0595.68072MR827723
  3. 3. B. COURCELLE, On Jump-Deterministic Pushdown Automata, Math. Systems Theory, Vol. 11, 1977, pp. 87-109. Zbl0365.02021MR464717
  4. 4. B. COURCELLE, A Representation of Trees by Languages I, Theoret. Comput. Sci., Vol. 6, 1978, pp. 255-279. Zbl0377.68040MR495225
  5. 5. B. COURCELLE, A Representation of Trees by Languages II, Theoret. Comput. Sci., Vol. 7, 1978, pp. 25-55. Zbl0428.68088MR495226
  6. 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. Zbl0342.68008MR411225
  7. 7. B. COURCELLE, Fundamental Properties of Infinite Trees, Theoret. Comput. Sci., Vol. 25, (2), 1983, pp. 95-170. Zbl0521.68013MR693076
  8. 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. Zbl0366.68053MR502290
  9. 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. Zbl0358.68109MR443445
  10. 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. Zbl0474.68065
  11. 11. S. GINSBURG and E. SPANIER, Finite-Turn Pushdown Automata, S.I.A.M. J. on Control, Vol. 4, (3), 1966, pp. 429-453. Zbl0147.25302MR204294
  12. 12. J. GOGUEN, J. THATCHER, E. WAGNER and J. WRIGHT, Initial Algebra Semantics, J.A.C.M., Vol. 24, 1977, pp. 68-95. Zbl0359.68018MR520711
  13. 13. S. GORN, Explicit Definitions and Linguistic Dominoes, in J. HART and S. TAKASU, Eds., Systems and Computer Science, University of Toronto Press, 1965. MR237245
  14. 14. I. GUESSARIAN, Algebraic Semantics, L.N.C.S., Vol. 99. Springer Verlag, 1981. Zbl0474.68010MR617908
  15. 15. M. A. HARRISON, Introduction to Formal Language Theory, Addison Wesley, Reading, Mass, 1978. Zbl0411.68058MR526397
  16. 16. M. A. HARRISON and I. M. HAVEL, Strict Deterministic Grammars, J. Comput. System Sci., Vol. 7, 1973, pp. 237-277. Zbl0261.68036MR319415
  17. 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. Zbl0267.68034MR323164
  18. 18. M. A. HARRISON and I. M. HAVEL, On the Parsing of Deterministic Languages, J.A.C.M., Vol. 21, 1974, pp. 525-548. Zbl0296.68084MR356589
  19. 19. M. NIVAT, On the Interpretation of Recursive Polyadic Program Schemes, Symposia Mathematica, Vol. 15, Academic Press, New York, 1975, pp. 255-281. Zbl0346.68041MR391563
  20. 20. M. OYAMAGUCHI and N. HONDA, The Decidability of Equivalence for Deterministic Stateless Pushdown Automata, Information and Control, Vol. 38, 1978, pp. 367-376. Zbl0393.68078MR509559
  21. 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. Zbl0393.68078MR582147
  22. 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. Zbl0473.68046MR644735
  23. 23. M. OYAMAGUCHI, The Equivalence Problem for Real-Time DPD A's, submitted for publication, 1986. Zbl0637.68094MR904202
  24. 24. L. G. VALIANT, Decision Procedures for Families of Deterministic Pushdown automata, Ph. D. thesis, University of Warwick, U.K., 1973. 
  25. 25. L. G. VALIANT, The Equivalence Problem for Deterministic Finite-Turn Pushdown Automata, Information and Control, Vol. 25, 1975, pp. 123-133. Zbl0285.68025MR391591

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.