The Relationship Between Tree Adjoining Grammars And Head Grammars

D.J. Weir K.Vijay-Shanker A.K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 Abstract 67 We examine the relationship between the two grammatical formalisms: Tree Adjoining Grammars and Head Gram- mars. We briefly investigate the weak equivalence of the two formalisms. We then turn to a discussion comparing the linguistic expressiveness of the two formalisms. 1 Introduction Recent work [9,3] has revealed a very close formal rela- tionship between the grammatical formalisms of Tree Ad- joining Grammars (TAG's) and Head Grammars (HG's). In this paper we examine whether they have the same power of linguistic description. TAG's were first intro- duced in 1975 by Joshi, Levy and Takahashi[1] and inves- tigated further in [2,4,8]. HG's were first introduced by Pollard[5]. TAG's and HG's were introduced to capture certain structural properties of natural languages. These formalisms were developed independently and are nota- tionally quite different. TAG's deal with a set of elemen- tary trees composed by means of an operation called ad- joining. HG's maintain the essential character of context- free string rewriting rules, except for the fact that besides concatenation of strings, string wrapping operations are permitted. Observations of similarities between proper- ties of the two formalisms led us to study the formal rela- tionship between these two formalisms and the results of this investigation are presented in detail in [9,3]. We will briefly describe the formal relationship established in [9,3], showing TAG's to be equivalent to a variant of HG's. We argue that the relationship between HG's and this variant of HG's called Modified Head Grammars (MHG's) is very close. Having discussed the question of the weak equivalence of TAG's and HG's, we explore, in Sections 4 and 5, what might be loosely described as their strong equivalence. Sec- tion 4 discusses consequences of the substantial notational differences between the two formalisms. In Section 5, with the use of several examples of analyses (that can not be t This work was partially supported by the NSF grants MCS-82-19116-CER, MCS-82-07294 and DCR-84-10413. We are grateful to Tony Kroch and Carl Pollard, both of whom have made valuable contributions to this work. given by CFG's), we attempt to give cases in which they have the ability to make similar analyses as well as situa- tions in which they differ in their descriptive power. 1.1 Definitions In this section, we shall briefly define the three formalisms: TAG's, HG's, and MHG's. 1.1.1 Tree Adjoining Grammars Tree Adjoining Grammars differs from string rewriting sys- tems such as Context Free Grammars in that they generate trees. These trees are generated from a finite set of so- called elementary trees using the operation of tree ad- junction. There are two types of elementary trees: initial and auxiliary. Linguistically, initial trees correspond to phrase structure trees for basic sentential forms, whereas auxiliary trees correspond to modifying structures. The nodes in the frontier of elementary trees are la- belled by terminal symbols except for one node in the fron- tier of each auxiliary tree, …

Content truncated to 500 words