General properties of derivational complexity

1. Blum, M.: A machine independent theory of the complexity of recursive functions. J. ACM 14, 322–336 (1967)

   Google Scholar 

2. Book, R.V.: Time-bounded grammars and their languages. J. Computer System Sci. 5, 391–429 (1971)

   Google Scholar 

3. Book, R.V.: Personal communication (1976)

4. Borodin, A.: Computational complexity and the existence of complexity gaps. J. ACM 19, 158–174 (1972)

   Google Scholar 

5. Ginsburg, S.: The mathematical theory of context-free languages. New York: McGraw-Hill 1966

   Google Scholar 

6. Gladkij, A.V.: On the complexity of derivations in immediate constituent grammars. Algebra Logika 3, 29–44 (1964)

   Google Scholar 

7. Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc. 17, 285–306 (1965)

   Google Scholar 

8. Hartmanis, J., Hopcroft, J.E.: An overview of the theory of computational complexity. J. ACM 18, 444–475 (1971)

   Google Scholar 

9. Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Reading (Mass.): Addison-Wesley 1969

   Google Scholar 

10. Igarashi, Y., Honda, N.: A classification of phrase structure languages. Trans. Institute Electronics Communication Engineers, Japan, 53-c, 462–468 (1970)

    Google Scholar 

11. Igarashi, Y., Honda, N.: Some properties of T(n)-derivable languages. Trans. Institute Electronics Communication Engineers, Japan, 53-c, 637–643 (1970)

    Google Scholar 

12. Rogers, H.: Theory of recursive functions and effective computability. New York: McGraw-Hill 1967

    Google Scholar 

13. Rogers, H.: Gödel numbering of partial recursive functions. J. Symbolic Logic 23, 331–341 (1958)

    Google Scholar 

14. Salomaa, A.: Formal languages. London-New York: Academic Press 1973

    Google Scholar 

15. Trakhtenbrot, B.A.: Complexity of algorithms and computations. Cource notes, Novosibirsk State University, Novosibirsk, 1967

    Google Scholar 

Download references