A theory of complexity of monadic recursion schemes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 15 (1981) no. 1, pp. 67-94.
@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},
pages = {67--94},
publisher = {EDP-Sciences},
volume = {15},
number = {1},
year = {1981},
zbl = {0469.68050},
mrnumber = {610946},
language = {en},
url = {http://www.numdam.org/item/ITA_1981__15_1_67_0/}
}
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
DA  - 1981///
SP  - 67
EP  - 94
VL  - 15
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1981__15_1_67_0/
UR  - https://zbmath.org/?q=an%3A0469.68050
UR  - https://www.ams.org/mathscinet-getitem?mr=610946
LA  - en
ID  - ITA_1981__15_1_67_0
ER  - 
Dikovskii, A. Ja. A theory of complexity of monadic recursion schemes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 15 (1981) no. 1, pp. 67-94. http://www.numdam.org/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