Some Computational Properties of Tree Adjoining Grammars

SOME COMPUTATIONAL PROPERTIES OF TREE ADJOINING GRAMMARS* K. Vijay-Shankltr and Ar~vlnd K. Joshl Department of Computer and Information Science Room 268 Moore School/D2 University of Pennsylvania Philadelphia, PA 191C4 .ABSTRACT Tree Adjoining Grammar (TAG) is a formalism for natural language grammars. Some of the basic notions of TAG's were introduced in [Joshi,Levy, and Takahashi 19751 and by [Joshi, 1083]. A detailed investigation of the linguistic relevance of TAG's has been carried out in [Kroch and Joshi,1985]. In this paper, we will describe some new results for TAG's, especially in the following areas: (I) parsing complexity of TAG's, (2) some closure results for TAG's, and (3) the relationship to Head grammars. 1. INTRODUCTION Investigation of constrained grammatical systems from the point of view of their linguistic adequacy and thei¢ computational tractability has been a major concern of computational linguists for the last several years. Generalized Phrase Structure grammars (GPSG), Lexical Functional grammars" (LFG), Phrase Linking grammars (PLG), and Tree Adjoining grammars (TAG) are some key examples of grammatical systems that have been and still continue to be investigated along these lines. Some of the basic notions of TAG% were introduced in [Joshi, Levy, and Takahashi,1975] and [Jo6hi,lQ83]. Some preliminary investigations of the linguistic relevance and some computational properties were also carried out in [Jo6hi,1983]. More recently, a detailed investigation of the linguistic relevance of TAG's were carried out by [Kroch and Joshi,1985]. In this paper, we will describe some new results for TAG's, especially in the following areas: (1) parsing complexity of TAG's, (2) some closure results for TAG's, and (3) the relationship to Head grammars. These topics will be covered in Sections 3, 4, and S respectively. In section 2, we will give an introduction to TAG's. In section 6, we will state some properties not discussed here. A detailed exposition of these results is given in [Vijay-Shankar and Joshi,1985]. "This work wu partially supported by NSF Grants MCS-821011e-CER. MCS-82~7204. We want to thuk Carl P'oUard, Kelly Roach, David SeaM, tad David Weir. We have benefited enormously by valuable dbcussion8 with them. 2. TREE ADJOINING GRAMMARS--TAG's We now introduce tree adjoining grammars (TAG's). TAG's are more powerful than CFG's, both weakly and strongly. ! TAG's were first introduced in [Joshi, Levy, and Takahashi,1O7$] and [Joshi,1983]. We include their description in this section to make the paper self-contained. We can define a tree ~ grammar as follows. A tree adjoining grammar G is'-~pair (I,A) where ] ~ a set of initial trees, and A is a set of auxiliary trees. A tree o is an initial tree if it is of the form CZ~ / /\ s \ ,6~" / \ / \ That L% the root node of a is labelled S and the frontier nodes are all terminal symbols. The internal nodes are aU non-terminaL. A tree ~ is an a~xiliary tree if it is of the form / \ / \ / \ -xvz E I \ v I v2 That is, the root node of ~0 m …

Content truncated to 500 words