Some Computational Properties of Tree Adjoining Grammars

SOME COMPUTATIONAL PROPERTISS OF TREE ADJOINING GRAMM.~.S* K. Vijay-Shank~" and Aravind K. Jouhi Department of Computer and Information ~eience Room 288 Moore School/D2 University of Pennsylvania Philadelphia~ PA 191Ct ABSTRACT Tree Adjoining Grammar (TAG) is u formalism for natural language grammars. Some of the basic notions of TAG's were introduced in [Jo~hi,Levy, mad Takakashi I~'Sl and by [Jo~hi, l~l. A detailed investigation of the linguistic relevance of TAG's has been carried out in IKroch and Joshi,1985~. In this paper, we will describe some new results for TAG's, espe¢ially 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 lnvestigatiou of constrained grammatical system from the point of view of their linguistic &leqnary and their computational tractability has been a mnjor concern of computational linguists for the last several years. Generalized Phrase Structure grammars (GPSG), Lexical Functional grunmmm (LFG), Phrm~ Linking grammars (PLG), and Tree Adjoining grammars (TAG) are some key examples of grammatical systems that have been and still continue to be investignted along theme lines. Some of the bask notions of TAG's were introduced in [Joahi, Levy, and Takahashi,1975] and [Jo~hi,198,3 I. Some pretiminav/ investigations of the linguistic relevance and some computational properties were also carried out in [Jo~hi, l~S3 I. More recently, a detailed iuvestigution of the linguistic relevance of TAG's were carried out by [Kro~h and Joshi, 19851. In this paper, we will des¢ribe 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 grammar*. These topics will be covered in Sections 3, 4, and $ 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-Sbuh~ and Joahi,1985[. *This work wu ptrtisJ~ su.~ported by NSP Gr~u~* Mk'TS-4~IOII6.~'~R, MCS42-07.~94. We wtat to thank Clr| Pol!ard. Kelly Rozeh, David Se~ tad David Weu'. We have beDeflt~l enormously I:y v*/uablo di~*eo~iotc with them. 82 2. TREE ADJOINING GRAMMARS--TAG's We now introduce tree adjoining grammars (TAG's). TAG's are more powerful than CFG's, botb weakly and strongly, l TAG's were first introduced in [Joshi, Levy, and Takahashi,1975J and [Joehi,1983 I. We include their description in this ~*ction to make the paper ~lf-contalned. We can define a tree adjoining grammar as follows. A tree adjoining grammar G is a paw (i,A) where i is a set of initial trees, and A is a set of auxiliary trees. A tree a ls an initial tree if it is of the form GI I S I\ I \ eE. r~ l \ I \ l That m, the root node of a is labelled S and the frontier nodes are all terminal symbob. The internal nodes are ~11 non-terminals. A tree ~ is an acxiliar? tree if it is of the form ~= X I \ I \ I \ wle= E …

Content truncated to 500 words