On the complexity of formal grammars

1. Book, R.: Grammars with time functions. Harvard University, Ph.D. Dissertation, 1969. Also appears as Mathematical Linguistics and Automatic Translation, NSF-23, Aiken Computation Laboratory, Harvard University, Cambridge, MA, 1969

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

   Google Scholar 

3. Book, R.: On the structure of context-sensitive grammars. Internat. J. Comput. Information Sci. 2, 129–139 (1973)

   Google Scholar 

4. Book, R.: Comparing complexity classes. J. Comput. System Sci. 9, 213–229 (1974)

   Google Scholar 

5. Book, R.: Translational lemmas, polynomial time, and (log n)^j-space. Theor. Comput. Sci. 1, 215–226 (1975)

   Google Scholar 

6. Cook, S.: The complexity of theorem-proving procedures. In: Proc. Third ACM Symposium on Theory of Computing, 1971, pp. 151–158

7. Fischer, M.: Grammars with macro-like productions. In: Conference Record Ninth IEEE Symp. Switching and Automata Theory, 1968, pp. 131–142

8. Gladkii, A.: On the complexity of derivations in phrase-structure grammars [in Russian]. Algebrai i Logika Sem. 3, 29–44 (1964)

   Google Scholar 

9. Greibach, S.: Checking automata and one-way stack languages. J. Comput. System Sci. 3, 196–217 (1969)

   Google Scholar 

10. Greibach, S.: Some restrictions on W-grammars. Internat J. Comput. Information Sci. 3, 289–327 (1974)

    Google Scholar 

11. Igarashi, Y.: General properties of derivational complexity. Acta Informat. 8, 267–283 (1977)

    Google Scholar 

12. Igarashi, Y., Honda, N.: On the extension of Gladkii's theorem and the hierarchies of languages. J. Comput. System Sci 7, 199–217 (1973)

    Google Scholar 

13. Karp, R.: Reducibilities among combinatorial problems. In: Complexity of computer computations (R. Miller, J. Thatcher, eds.). New York: Plenum Press 1972

    Google Scholar 

14. Kuroda, S.-Y.: Classes of languages and linear-bounded automata. Information and Control 7, 207–223 (1964)

    Google Scholar 

15. Landweber, P.: Three theorems on phrase-structure grammars. Information and Control 6, 131–136 (1963)

    Google Scholar 

16. Rounds, W.: Complexity of recognition in intermediate-level languages. In: Conf. Record Fourteenth IEEE Symp. Switching and Automata Theory, 1973, pp. 145–158

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

    Google Scholar 

18. Shamir, E., Beeri, C.: Checking stacks and context-free programmed grammars accept p-complete languages. In: Proc. 2nd Colloquium on Automata Languages, and Programming. Lecture notes in computer science, Vol. 14, pp. 27–33. Berlin-Heidelberg-New York: Springer 1974

    Google Scholar 

19. van Leeuwen, J.: The membership question for ETOL-languages is polynomially complete. Information Processing Lett. 3, 138–143 (1975)

    Google Scholar 

20. van Leeuwen, J..: Extremal properties of non-deterministic time-complexity classes. In: International Computing Symposium 1975 (E. Gelenbe, D. Potier, eds.), pp. 61–64. Amsterdam: North Holland 1975

    Google Scholar 

Download references