×

zbMATH — the first resource for mathematics

A hierarchy between context-free and context-sensitive languages. (English) Zbl 0212.02705

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Rosenkrantz, D.J., Programmed grammars and classes of formal languages, J. assoc. comput. Mach., 16, 107-131, (1969) · Zbl 0182.02004
[2] Ábrahám, S., Some questions of phrase structure grammars I, Comput. linguist., 4, 61-70, (1965)
[3] Brainerd, B., An analog of a theorem about context-free languages, Information and control, 11, 561-567, (1968) · Zbl 0184.02601
[4] Greibach, S.; Hopcroft, J., Scattered context grammars, J. comput. system sci., 3, 233-247, (1969) · Zbl 0174.02801
[5] Friš, I., Grammars with partial ordering of the rules, Information and control, 12, 415-425, (1968) · Zbl 0172.30002
[6] \scE. Moriya, State grammars, ordered grammars, and matrix grammars, in preparation. · Zbl 0264.68028
[7] Ginsburg, S.; Greibach, S.A., Abstract families of languages, (), 1-32 · Zbl 0308.68058
[8] Ginsburg, S., ()
[9] Ginsburg, S.; Spanier, E.H., Control sets on grammars, Math. systems theory, 2, 159-177, (1968) · Zbl 0157.33604
[10] Ginsburg, S.; Greibach, S.A., Mapping which preserve context sensitive languages, Information and control, 9, 563-582, (1966) · Zbl 0145.00803
[11] Kuroda, S.Y., Classes of languages and linear-bounded automata, Information and control, 7, 207-223, (1964) · Zbl 0199.04002
[12] Greibach, S.; Hopcroft, J., Independence of AFL operations, (), 33-40
[13] Matthews, G.H., A note on asymmetry in phrase structure grammars, Information and control, 7, 360-365, (1964) · Zbl 0134.24603
[14] Parikh, R.J., On context-free languages, J. assoc. comput. Mach., 13, 570-581, (1966) · Zbl 0154.25801
[15] Bar-Hillel, Y.; Perlis, M.; Shamir, E., On formal properties of simple phrase structure grammars, Z. phonetik sprachwiss. kommunikat., 14, 143-172, (1961) · Zbl 0106.34501
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.