A theory of complexity of monadic recursion schemes

Dikovskii, A. Ja.

Dikovskii, A. Ja.

RAIRO. Informatique théorique, Tome 15 (1981) no. 1, pp. 67-94

MR Zbl

@article{ITA_1981__15_1_67_0,
     author = {Dikovskii, A. Ja.},
     title = {A theory of complexity of monadic recursion schemes},
     journal = {RAIRO. Informatique th\'eorique},
     pages = {67--94},
     year = {1981},
     publisher = {EDP Sciences},
     volume = {15},
     number = {1},
     mrnumber = {610946},
     zbl = {0469.68050},
     language = {en},
     url = {https://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. Informatique théorique
PY  - 1981
SP  - 67
EP  - 94
VL  - 15
IS  - 1
PB  - EDP Sciences
UR  - https://www.numdam.org/item/ITA_1981__15_1_67_0/
LA  - en
ID  - ITA_1981__15_1_67_0
ER  -

%0 Journal Article
%A Dikovskii, A. Ja.
%T A theory of complexity of monadic recursion schemes
%J RAIRO. Informatique théorique
%D 1981
%P 67-94
%V 15
%N 1
%I EDP Sciences
%U https://www.numdam.org/item/ITA_1981__15_1_67_0/
%G en
%F ITA_1981__15_1_67_0

Dikovskii, A. Ja. A theory of complexity of monadic recursion schemes. RAIRO. Informatique théorique, Tome 15 (1981) no. 1, pp. 67-94. https://www.numdam.org/item/ITA_1981__15_1_67_0/

Bibliographie
Cité par

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

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

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

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

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

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

8. A. Ja. Dikovskii, Classifications of Context-Free Languages by Dérivation Complexity (submitted for publication in Semiotika i informatika) (Russ.). | Zbl

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

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

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

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