×

zbMATH — the first resource for mathematics

The equivalence of four extensions of context-free grammars. (English) Zbl 0813.68129
Summary: There is currently considerable interest among computational linguists in grammatical formalism with highly restricted generative power. This paper concerns the relationship between the class of string languages generated by several such formalisms, namely, combinatory categorical grammars, head grammars, linear indexed grammars, and tree adjoining grammars. Each of these formalisms is known to generate a larger class of languages than context-free grammars. The four formalisms under consideration were developed independently and appear superficially to be quite different from one another. The result presented in this paper is that all four of the formalisms under consideration generate exactly the same class of string languages.

MSC:
68Q42 Grammars and rewriting systems
68T50 Natural language processing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. V. Aho. Indexed grammars?an extension to context free grammars.J. Assoc. Comput. Mach.,15:647-671, 1968. · Zbl 0175.27801
[2] K. Ajdukiewicz. Die syntaktische Konnexität.Studia Philosophica,1:1-27, 1935. English translation in: S. McCall, editor,Polish Logic, 1920-1939, pp. 207-231. Oxford University Press, Oxford. · Zbl 0015.33702
[3] C. Culy. The complexity of the vocabulary of bambara.Ling. Philos.,8:345-351, 1985.
[4] J. Duske and R. Parchmann. Linear indexed languages.Theoret. Comput. Sci.,32:47-60, 1984. · Zbl 0545.68067
[5] G. Gazdar. Applicability of indexed grammars to natural languages. In: U. Reyle and C. Rohrer, editors,Natural Language Parsing and Linguistic Theories, pp. 69-94. Reidel, Dordrecht, 1988.
[6] G. Gazdar, E. Klein, G. K. Pullum, and I. A. Sag.Generalized Phrase Structure Grammars. Blackwell, Oxford, 1985. Also published by Harvard University Press, Cambridge, MA.
[7] A. K. Joshi. How much context-sensitivity is necessary for characterizing structural descriptions ?Tree Adjoining Grammars? In: D. Dowty, L. Karttunen, and A. Zwicky, editors,Natural Language Processing?Theoretical, Computational and Psychological Perspective, pp. 206-250. Cambridge University Press, New York, 1985. Originally presented in 1983.
[8] A. K. Joshi, L. S. Levy, and M. Takahashi. Tree adjunct grammars.J. Comput. System Sci.,19(1):136-163, 1975. · Zbl 0326.68053
[9] T. Kasami. An efficient recognition and syntax algorithm for context-free languages. Technical Report AF-CRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA, 1965.
[10] A. S. Kroch. Asymmetries in long distance extraction in a tag grammar. In: M. Baltin and A. S. Kroch, editors,New Conceptions of Phrase Structure, pp. 66-98. University of Chicago Press, Chicago, IL, 1986.
[11] A. S. Kroch. Subjacency in a tree adjoining grammar. In: A. Manaster-Ramer, editor,Mathematics of Language, pp. 143-172. Benjamins, Amsterdam, 1987.
[12] A. S. Kroch and A. K. Joshi. Linguistic relevance of tree adjoining grammars. Technical Report MS-CIS-85-18, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, 1985.
[13] A. S. Kroch and A. K. Joshi. Analyzing extraposition in a tree adjoining grammar. In: G. Huck and A. Ojeda, editors,Syntax and Semantics: Discontinuous Constituents, pp. 107-149. Academic Press, New York, 1986.
[14] A. S. Kroch and B. Santorini. The derived constituent structure of West Germanic verb-raising construction. In: R. Freiden, editor,Proceedings of the Princeton Workshop on Grammar, pp. 269-338, 1991.
[15] C. Pollard. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language. Ph.D. thesis, Stanford University, CA, 1984.
[16] G. Pullum and G. Gazdar. Natural languages and context-free languages.Ling. Philos.,4:471-504, 1982.
[17] K. Roach. Formal properties of head grammars. In: A. Manaster-Ramer, editor,Mathematics of Language, pp. 293-348. Benjamins, Amsterdam, 1987.
[18] B. Santorini. The West Germanic verb-raising construction: a tree adjoing grammar analysis. Master’s thesis, University of Pennsylvania, Philadelphia, PA, 1986.
[19] S. M. Shieber. Evidence against the context-freeness of natural language.Ling. Philos.,8:333-343, 1985.
[20] M. J. Steedman. Dependency and coordination in the grammar of Dutch and English.Language,61:523-568, 1985.
[21] M. J. Steedman. Combinators and grammars. In: R. Oehrle, E. Bach, and D. Wheeler, editors,Categorial Grammars and Natural Language Structures, pp. 417-442. Foris, Dordrecht, 1986.
[22] K. Vijay-Shanker. A study of tree adjoining grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA, 1987.
[23] K. Vijay-Shanker and D. J. Weir. Parsing constrained grammar formalisms.Comput. Linguistics, to appear.
[24] K. Vijay-Shanker and D. J. Weir. Polynomial parsing of extensions of context-free grammars. In: M. Tomita, editor,Current Issues in Parsing Technology, pp. 191-206. Kluwer, Boston, 1991.
[25] K. Vijay-Shanker, D. J. Weir, and A. K. Joshi. Tree adjoining and head wrapping.Proceedings of the 11th International Conference on Computational Linguistics, pp. 202-207, 1986.
[26] D. J. Weir. Characterizing mildly context-sensitive grammar formalisms. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA, 1988.
[27] D. J. Weir. A geometric hierarchy beyond context-free languages.Theoret. Comput. Sci.,104:235-261, 1992. · Zbl 0754.68070
[28] D. J. Weir and A. K. Joshi. Combinatory categorial grammars: generative power and relationship to linear context-free rewriting systems.Proceedings of the 26th Meeting of the Association on Computational Linguistics, pp. 278-285, 1988.
[29] D. H. Younger. Recognition and parsing of context-free languages in timen 3.Inform. and Control,10(2):189-208, 1967. · Zbl 0149.24803
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.