×

zbMATH — the first resource for mathematics

Size, index, and context-sensitivity of controlled partition grammars. (English) Zbl 0364.68078
MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Abraham, Some Questions of Phrase Structure Grammars,Computational Linguistics 4 (1965), 61–70.
[2] A. Aho, Indexed Grammars, an Extension of Context-Free Grammars,JACM 15 (October 1968), 647–671. · Zbl 0175.27801 · doi:10.1145/321479.321488
[3] N. Chomsky, On Certain Formal Properties of Grammars,Information and Control 2 (June 1959), 137–167. · Zbl 0088.10801 · doi:10.1016/S0019-9958(59)90362-6
[4] N. Chomsky,Aspects of the Theory of Syntax, The MIT Press, Cambridge, Mass. 1965.
[5] A. B. Cremers, Normal Forms for Context-Sensitive Grammars,Acta Informatica 3 (1973), 59–73. · Zbl 0285.68040 · doi:10.1007/BF00288653
[6] A. B. Cremers andO. Mayer, On Matrix Languages,Information and Control 23 (1973), 86–96. · Zbl 0263.68039 · doi:10.1016/S0019-9958(73)90917-0
[7] A. B. Cremers andO. Mayer, On Vector Languages,J. Computer and System Sciences 8 (1974), 158–166. · Zbl 0277.68043 · doi:10.1016/S0022-0000(74)80053-X
[8] A. B. Cremers, H. A. Maurer, andO. Mayer, A Note on Leftmost Restricted Random Context Grammars,Information Processing Letters 2 (1973), 31–33. · Zbl 0261.68038 · doi:10.1016/0020-0190(73)90008-2
[9] I. Fris, Grammars with Partial Ordering of the Rules,Information and Control 12 (1968), 415–425. · Zbl 0172.30002 · doi:10.1016/S0019-9958(68)90439-7
[10] S. Ginsburg andB. H. Partee, A Mathematical Model of Transformational Grammars,Information and Control 15 (October 1969), 297–334. · Zbl 0207.01501 · doi:10.1016/S0019-9958(69)90464-1
[11] S. Ginsburg andE. H. Spanier, Control Sets on Grammars,Math. Systems Theory 2 (1968), 159–177. · Zbl 0157.33604 · doi:10.1007/BF01692513
[12] S. A. Greibach andJ. E. Hopcroft, Scattered Context Grammars,J. Computer and System Sciences 3 (1969), 233–247. · Zbl 0174.02801 · doi:10.1016/S0022-0000(69)80015-2
[13] J. E. Hopcroft andJ. D. Ullman,Formal Languages and their Relation to Automata, Reading, Mass., Addison-Wesley, 1969. · Zbl 0196.01701
[14] T. Kasai, An Hierarchy Between Context-Free and Context-Sensitive Languages,J. Computer and System Sciences 4 (1970), 492–508. · Zbl 0212.02705 · doi:10.1016/S0022-0000(70)80045-9
[15] S.-Y. Kuroda, Classes of Languages and Linear-Bounded Automata,Information and Control 7 (1964), 207–223. · Zbl 0199.04002 · doi:10.1016/S0019-9958(64)90120-2
[16] H. A. Maurer, Simple Matrix Languages with a Leftmost Restriction,Information and Control 23 (1973), 128–139. · Zbl 0261.68037 · doi:10.1016/S0019-9958(73)90627-X
[17] O. Mayer, Some Restrictive Devices for Context-Free Grammars,Information and Control 20 (1972), 69–92. · Zbl 0248.68035 · doi:10.1016/S0019-9958(72)90287-2
[18] D. L. Milgram andA. Rosenfeld, A Note on Scattered Context Grammars,Information Processing Letters 1 (1971), 47–50. · Zbl 0227.68040 · doi:10.1016/0020-0190(71)90004-4
[19] B. O. Nash, Context-Free Parallel-Levelled Grammars, Ph.D. Thesis, University of Waterloo, Ontario 1970.
[20] S. Peters andR. Ritchie, On the Generative Power of Transformational Grammar,Information Sciences 6 (1973), 49–83. · Zbl 0251.68045 · doi:10.1016/0020-0255(73)90027-3
[21] G. Rozenberg, Direction Controlled Programmed Grammars,Acta Informatica 1 (1972), 242–252. · Zbl 0244.68037 · doi:10.1007/BF00288688
[22] D. J. Rosenkrantz, Programmed Grammars and Classes of Formal Languages,JACM 16 (1969), 107–131. · Zbl 0182.02004 · doi:10.1145/321495.321504
[23] A. Salomaa, Periodically Time-Variant Context-Free Grammars,Information and Control 17 (1970), 294–311. · Zbl 0222.68032 · doi:10.1016/S0019-9958(70)90464-X
[24] A. Salomaa, Matrix Grammars with a Leftmost Restriction,Information and Control 20 (1972), 143–149. · Zbl 0241.68033 · doi:10.1016/S0019-9958(72)90332-4
[25] A. Salomaa,Formal Languages, New York, Academic Press, 1973. · Zbl 0262.68025
[26] W. Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities,J. Computer and System Sciences 4 (1970), 177–192. · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X
[27] J. van Leeuwen, A Partial Solution to the Reachability Problem for Vector Addition Systems,6th Ann. ACM Symp. on Theory of Computing (May 1974), 303–309.
[28] E.-M. M. Wotschke, Ordered Grammars with Equivalence Classes: Some Formal and Linguistic Aspects, Ph.D. Thesis, University of California, Los Angeles, 1975.
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.