On the structure of context-sensitive grammars

1. S. Abraham, “Some questions of phrase-structure grammars,”Comp. Linguistics 4:61–70 (1965).

   Google Scholar 

2. B. Baker, “Arbitrary grammars generating context-free languages,”Info. and Control, to appear.

3. D. Benson, “Syntax and semantics: a categorical view,”Info. and Control 17:145–160 (1970).

   Google Scholar 

4. R. Book, “Time-bounded grammars and their languages,”J. Computer and System Sci. 5:397–429 (1971).

   Google Scholar 

5. R. Book, “Terminal context in context-sensitive grammars,”SIAM J. Computing 1:20–30 (1972).

   Google Scholar 

6. N. Chomsky, “Formal properties of grammars,” inHandbook of Mathematical Psychology, Vol. II, R. D. Luce, Bush, and Galanter, Eds. (Wiley, New York, 1963).

   Google Scholar 

7. R. Evey, “The theory and application of pushdown store machines,” Ph.D. Dissertation, Harvard Univ., 1963; appears as “Math. Linguistics and Automatic Translation,” NSF-10 (1963), Computation Lab., Harvard Univ., Cambridge, Mass.

8. S. Ginsburg,The Mathematical Theory of Context-Free Languages (McGraw-Hill, New York, 1966).

   Google Scholar 

9. S. Ginsburg and S. A. Greibach, “Mappings which preserve context-sensitive languages,”Info. and Control 9:563–582 (1966).

   Google Scholar 

10. S. Ginsburg and S. A. Greibach, “Abstract families of languages,”Memoir, Am. Math. Soc. 87:1–32 (1969).

    Google Scholar 

11. A. Gladkii, “Grammars with linear memory” (in Russian),Algebri i Logika Sem. 2:43–55 (1963).

    Google Scholar 

12. A. Gladkii, “On the complexity of derivations in phrase-structure grammars” (in Russian),Algebri i Logika Sem. 3:29–44 (1964).

    Google Scholar 

13. T. Griffiths, “Some remarks on derivations in general rewriting systems,”Info. and Control 12:27–54 (1968).

    Google Scholar 

14. L. Haines, “Representation theorems for context-sensitive languages,” unpublished manuscript.

15. M. Harrison, “On the relation between grammars and automata,” inInformation Systems Science, Vol. 4, J. Tou, Ed. (Plenum, New York, 1972), pp. 39–92.

    Google Scholar 

16. M. Harrison and M. Schkolnick, “A grammatical characterization of one-way nondeterministic stack languages,”J. ACM 18:148–172 (1971).

    Google Scholar 

17. T. Hibbard, “Scan-limited automata and context-limited grammars,” Ph.D. Dissertation, Univ. of California, Los Angeles, 1966.

    Google Scholar 

18. S.-Y. Kuroda, “Classes of languages and linear-bounded automata,”Info. and Control 7:207–223 (1964).

    Google Scholar 

19. G. H. Matthews, “A note on asymmetry in phrase-structure grammars,”Info. and Control 7:360–365 (1964).

    Google Scholar 

20. G. H. Matthews, “Two-way languages,”Info. and Control 10:111–119 (1967).

    Google Scholar 

21. D. Rosenkrantz, “Programmed grammars and classes of formal languages,”J. ACM 16:107–131 (1969).

    Google Scholar 

22. A. Salomaa, “On grammars with restricted use of productions,”Ann. Acad. Sci. Fenn., Ser. A 1969, No. 454.

23. A. Salomaa, “On some families of formal languages obtained by regulated derivations,”Ann. Acad. Sci. Fenn., Ser. A 1970, No. 479.

24. W. Savitch, “Normal form theorems for phrase structure grammars,” Presented atSixth Princeton Conf. on Info. Sci. and Systems, 1972.

25. W. Sillars, “Formal properties of essentially context-dependent languages,” Ph.D. Dissertation, Pennsylvania State Univ., 1968.

26. J. Thatcher, “Characterizing derivation trees of context-free grammars through a generalization of finite automata theory,”J. Computer and System Sci. 1:317–322 (1967).

    Google Scholar 

27. B. Wegbreit, “A generator of context-sensitive languages,”J. Computer and System Sci. 3:456–461 (1969).

    Google Scholar 

28. A. Aho, “Indexed grammars—An extension of context-free grammars,”J. ACM 15:647–671 (1968).

    Google Scholar 

29. M. Fischer, “Grammars with macrolike productions,” Ph.D. Dissertation, Harvard Univ., Cambridge, Massachusetts, 1968.

    Google Scholar 

Download references