Tree Adjoining and Head Wrapping

Tree Adjoining and Head Wrapping~ K. Vijay-Shanker David J. Weir Aravind K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 Abstract In this paper we discuss the formal relationship between the classes of languages generated by Tree Adjoining Gram- mars and Head Grammars. In particular, we show that Head Languages are included in Tree Adjoining Languages and that Tree Adjoining Grammars are equivalent to a modifi- cation of Head Grammars called Modified Head Grammars. The inclusion of MHL in HL, and thus the equivalence of HG's and TAG's, in the most general case remains to be established. 1. Introduction This paper discusses the relationstfip between Tree Adjoin- ing Grammars (TAG's) and :Head Grammars (HG's). TAG's and HG's, introduced to capture certain structural prop- erties of natural languages, were developed independently. TAG's deal with a set of elementary trees which are com- posed by means of an operation called adjoining. HG's are like Context-free Grammars, except for the fact that besides concatenation of strings, string wrapping operations are permitted. TAG's were first introduced in 1975 by Joshi, Levy and Wakahashi [3]. Joshi [2] investigated some formal and linguistic properties of TAG's with local constraints. The formulation of local constraints was then modified and formal properties were investigated by Vijay-Shanker and Joshi [9]. The linguistic properties were studied in detail by Kroeh and Joshi [5]. HG's were first introduced by Pol- lard [6] in 1983 and their formal properties were investigated by Roach [7]. It was observed that the two systems seemed to possess similar generative power and since they also ap- pear to have the same closure properties [7,9] as well as similar parsing algorithn~ [6,9] a significant amount of in- direct evidence existed to suggest that they were formally equivalent. In the present paper, we will attempt to provide a characterization of the formal relationship between HG's and TAG's. In [10] we consider various linguistic aspects of the relationship: in particular what might be referred to as the strong equivalence of the two formalisms. Vijay-Shanker and Joshi [9] provided a brief description of the intuition behind the inclusion of Tree Adjoining Lan- gages (TAL) in the class of languages generated by a variant of HG's called Modified Head Grammars (MHG's). In the present paper, we give a proof of this result as well as a proof for the inclusion of Modified Head Languages (MHL) in TAL: hence we show that MHG's and TAG's are equiva- lent. This result is presented in section 3. In section 2, we discuss the relationship between MHG's and HG's. J" This work was partially supported by NSF grants MCS- 82-19116-CER, MCS-82-07294 and DC1~-84-10413. We are grateful bo Tony Kroch and Carl Pollard for valuable discus~ sions. 1.1. '.£ree Adjoining Grammars Definition 1. A TAG is a 54uple G -= (VN,V.r,S,I,A) where Vlv and V T are finite sets of nonterminals and ter- minals respectively, S is a distinguished nonterminal, I is a finite set of initial trees and A is …

Content truncated to 500 words