A theory of complexity of monadic recursion schemes
Dikovskii, A. Ja.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 15 (1981), p. 67-94 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1981-01-01
@article{ITA_1981__15_1_67_0,
     author = {Dikovskii, A. Ja.},
     title = {A theory of complexity of monadic recursion schemes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {15},
     year = {1981},
     pages = {67-94},
     mrnumber = {610946},
     zbl = {0469.68050},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1981__15_1_67_0}
}

Dikovskii, A. Ja. A theory of complexity of monadic recursion schemes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 15 (1981) pp. 67-94. http://gdmltest.u-ga.fr/item/ITA_1981__15_1_67_0/

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

2. K. Weihrauch, The Computational Complexity of Program Schemata, J. Comput. Syst. Sc., Vol. 12, 1976, pp. 80-107. | MR 400790 | Zbl 0321.68036

3. Y. Igarashi, On the Complexity of Generalized Monadic Recursion Schemes, Systems. Computers. Controls, Vol. 5, 1974, pp.18-25. | MR 403288

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

5. Sh. A. Greibach, Theory of Program Structures: Schemes, Semantics, Verification, Lecture Notes in Comput. Sc.,Vol. 36, 1975. | MR 431768 | Zbl 0345.68002

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.). | MR 663229

8. A. Ja. Dikovskii, Classifications of Context-Free Languages by Dérivation Complexity (submitted for publication in Semiotika i informatika) (Russ.). | Zbl 0482.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. | MR 256911 | Zbl 0182.57702

11. A. Ja. Dikovskii, Languages of Bounded Active Capacity, Soviet Math. Dokl., Vol. 11, 1970, pp. 748-750. | Zbl 0209.31002

12. A. Ja. Dikovskii, Density of Derivation Trees and Active Capacity of Grammars, Problemy peredaci informacii, Vol. 8, 1972, pp. 88-98 (Russ.). | MR 334587 | Zbl 0357.68080

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