A theory of complexity of monadic recursion schemes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1981)
- Volume: 15, Issue: 1, page 67-94
- ISSN: 0988-3754
Access Full Article
top
How to cite
topDikovskii, A. Ja.. "A theory of complexity of monadic recursion schemes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 15.1 (1981): 67-94. <http://eudml.org/doc/92136>.
@article{Dikovskii1981,
author = {Dikovskii, A. Ja.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {program schemes; complexity hierarchies; context-free grammars; mimeoinvariant complexity measures},
language = {eng},
number = {1},
pages = {67-94},
publisher = {EDP-Sciences},
title = {A theory of complexity of monadic recursion schemes},
url = {http://eudml.org/doc/92136},
volume = {15},
year = {1981},
}
TY - JOUR
AU - Dikovskii, A. Ja.
TI - A theory of complexity of monadic recursion schemes
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1981
PB - EDP-Sciences
VL - 15
IS - 1
SP - 67
EP - 94
LA - eng
KW - program schemes; complexity hierarchies; context-free grammars; mimeoinvariant complexity measures
UR - http://eudml.org/doc/92136
ER -
References
top- 1. R. L. CONSTABLE, Type Two Computational Complexity, in Proceedings of the Fifth Annual A.C.M. Symposium on the Theory of Computing, May 1973. Zbl0306.68022MR416106
- 2. K. WEIHRAUCH, The Computational Complexity of Program Schemata, J. Comput. Syst. Sc., Vol. 12, 1976, pp. 80-107. Zbl0321.68036MR400790
- 3. Y. IGARASHI, On the Complexity of Generalized Monadic Recursion Schemes, Systems. Computers. Controls, Vol. 5, 1974, pp.18-25. MR403288
- 4. St. J. GARLAND and D. C. LUCKHAM, Program Schemes, Recursion Schemes, and Formal Languages, J. Comput. Syst. Sc., Vol. 7, 1973, pp. 119-160. Zbl0277.68010MR315930
- 5. Sh. A. GREIBACH, Theory of Program Structures: Schemes, Semantics, Verification, Lecture Notes in Comput. Sc.,Vol. 36, 1975. Zbl0345.68002MR431768
- 6. A. Ja. DIKOVSKII, General Theory of Derivation Complexity and Syntactic Description in Context-Free Grammars, in A. V. GLADKII, Formal Grammars and Languages, Nauka, M., 1973, 9th chapter added in translation (submitted for translation into English in North-Holland Publishing Co.).
- 7. A. Ja. DIKOVSKII, A General Notion of Complexity of Derivation and Syntactic Description in Context-Free Grammar, in Semiotika i informatika, Vol. 7, M., 1977, pp. 83-105 (Russ.). MR663229
- 8. A. Ja. DIKOVSKII, Classifications of Context-Free Languages by Dérivation Complexity (submitted for publication in Semiotika i informatika) (Russ.). Zbl0482.68068
- 9. A. Ja. DIKOVSKII, Derivation Complexity of Unambiguous Context-Free Grammars and Languages (submitted for publication in Semiotika i informatika) (Russ.).
- 10. F. HARARY, Graph Theory, Addison-Wesley Publ. Co., Reading, Mass., 1969. Zbl0182.57702MR256911
- 11. A. Ja. DIKOVSKII, Languages of Bounded Active Capacity, Soviet Math. Dokl., Vol. 11, 1970, pp. 748-750. Zbl0209.31002
- 12. A. Ja. DIKOVSKII, Density of Derivation Trees and Active Capacity of Grammars, Problemy peredaci informacii, Vol. 8, 1972, pp. 88-98 (Russ.). Zbl0357.68080MR334587
- 13. A. V. GLADKY, Formal Grammars and Languages, Nauka, M., 1973 submitted for translation from Russian into English in North-Holland Publ. Co.).
- 14. W. OGDEN, A Helpful Result for Proving Inherent Ambiguity, Math. Syst. Theory, Vol. 2, 1968, pp. 191-194. Zbl0175.27802MR233645
NotesEmbed ?
topYou 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.