×

zbMATH — the first resource for mathematics

Normal forms for context-sensitive grammars. (English) Zbl 0285.68040

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ábrahám, S.: Some questions of phrase structure grammars. Computational Linguistics 4, 61-70 (1965)
[2] Book, R. V.: On the structure of context-sensitive grammars. Center for Res. in Comp. Tech., Harvard University, Cambridge (Mass.), TR 6-71, 1971 · Zbl 0266.68038
[3] Cremers, A. B., Mayer, O.: On matrix languages. Information and Control 23, 86-96 (1973) · Zbl 0263.68039 · doi:10.1016/S0019-9958(73)90917-0
[4] Cremers, A. B., Mayer, O.: On vector languages. J. Computer and System Sciences, to appear, 1973 · Zbl 0263.68039
[5] Cremers, A. B., Maurer, H. A., Mayer, O.: A note on leftmost restricted random context grammars. Information Processing Letters 2, 31-33 (1973) · Zbl 0261.68038 · doi:10.1016/0020-0190(73)90008-2
[6] Ginsburg, S.: The mathematical theory of context-free languages. New York: McGraw-Hill 1966 · Zbl 0184.28401
[7] Ginsburg, S., Spanier, E. H.: Control sets on grammars. Math. Systems Theory 2, 159-177 (1968) · Zbl 0157.33604 · doi:10.1007/BF01692513
[8] Greibach, S. A., Hopcroft, J. E.: Scattered context grammars. J. Computer and System Sciences 3, 233-247 (1969) · Zbl 0174.02801 · doi:10.1016/S0022-0000(69)80015-2
[9] Hopcroft, J. E., Ullman, J. D.: Formal languages and their relation to automata. Reading (Mass.): Addison-Wesley 1969 · Zbl 0196.01701
[10] Kasai, T.: An hierarchy between context-free and context-sensitive languages. J. Computer and System Sciences 4, 492-508 (1970) · Zbl 0212.02705 · doi:10.1016/S0022-0000(70)80045-9
[11] Kuroda, S.-Y.: Classes of languages and linear-bounded automata. Information and Control 7, 207-223 (1964) · Zbl 0199.04002 · doi:10.1016/S0019-9958(64)90120-2
[12] Levitina, M. K.: On some grammars with global productions. (In Russian) Akad. Nauk SSSR Nauchno-Tekhn. Inform. Ser. 2, 32-36 (1972)
[13] Lomkovskaya, M. V.: On some properties of k-conditional grammars. (In Russian) Akad. Nauk SSSR Nauchno-Tekhn. Inform. Ser. 2, 61-21 (1972) · Zbl 0232.68031
[14] Maurer, H. A.: Simple matrix languages with a leftmost restriction. Information and Control, to appear, 1973 · Zbl 0261.68037
[15] Mayer, O.: Some restrictive devices for context-free grammars. Information and Control 20, 69-92 (1972) · Zbl 0248.68035 · doi:10.1016/S0019-9958(72)90287-2
[16] Milgram, D. L., Rosenfeld, A.: A note on scattered context grammars. Information Processing Letters 1, 47-50 (1971) · Zbl 0227.68040 · doi:10.1016/0020-0190(71)90004-4
[17] Rozenberg, G.: Direction controlled programmed grammars. Acta Informatica 1, 242-252 (1972) · Zbl 0244.68037 · doi:10.1007/BF00288688
[18] Rosenkrantz, D. J.: Programmed grammars and classes of formal languages. J. ACM 16, 107-131 (1969) · Zbl 0182.02004 · doi:10.1145/321495.321504
[19] Salomaa, A.: Periodically time-variant context-free grammars. Information and Control 17, 294-311 (1970) · Zbl 0222.68032 · doi:10.1016/S0019-9958(70)90464-X
[20] Salomaa, A.: Matrix grammars with a leftmost restriction. Information and Control 20, 143-149 (1972) · Zbl 0241.68033 · doi:10.1016/S0019-9958(72)90332-4
[21] Salomaa, A.: Formal languages. New York: Academic Press 1973 · Zbl 0262.68025
[22] Stotskij, E. D.: On grammars with rules of a special form. (In Russian) Akad. Nauk SSSR Nauchno-Tekhn. Inform. Ser. 2, 34-37 (1971) · Zbl 0274.68019
[23] Stotskij, E. D.: Remarks on the paper by M. K. Levitina. (In Russian) Akad. Nauk SSSR Nauchno-Tekhn. Inform. Ser. 2, 37 (1972)
[24] Van der Walt, A. P. J.: Random context languages. Symp. on Formal Languages, Oberwolfach, Germany 1970 · Zbl 0221.68047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.