Efficiently Parsable Extensions to Tree-Local Multicomponent TAG

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 92–100, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Efficiently Parsable Extensions to Tree-Local Multicomponent TAG Rebecca Nesson School of Engineering and Applied Sciences Harvard University Cambridge, MA nesson@seas.harvard.edu Stuart M. Shieber School of Engineering and Applied Sciences Harvard University Cambridge, MA shieber@seas.harvard.edu Abstract Recent applications of Tree-Adjoining Gram- mar (TAG) to the domain of semantics as well as new attention to syntactic phenomena have given rise to increased interested in more ex- pressive and complex multicomponent TAG formalisms (MCTAG). Although many con- structions can be modeled using tree-local MCTAG (TL-MCTAG), certain applications require even more flexibility. In this pa- per we suggest a shift in focus from con- straining locality and complexity through tree- and set-locality to constraining locality and complexity through restrictions on the deriva- tional distance between trees in the same tree set in a valid derivation. We examine three formalisms, restricted NS-MCTAG, restricted Vector-TAG and delayed TL-MCTAG, that use notions of derivational distance to con- strain locality and demonstrate how they permit additional expressivity beyond TL- MCTAG without increasing complexity to the level of set local MCTAG. 1 Introduction Tree-Adjoining Grammar (TAG) has long been pop- ular for natural language applications because of its ability to naturally capture syntactic relationships while also remaining efficient to process. More re- cent applications of TAG to the domain of seman- tics as well as new attention to syntactic phenomena such as scrambling have given rise to increased in- terested in multicomponent TAG formalisms (MC- TAG), which extend the flexibility, and in some cases generative capacity of the formalism but also have substantial costs in terms of efficient process- ing. Much work in TAG semantics makes use of tree-local MCTAG (TL-MCTAG) to model phenom- ena such as quantifier scoping, Wh-question forma- tion, and many other constructions (Kallmeyer and Romero, 2004; Romero et al., 2004). Certain ap- plications, however, appear to require even more flexibility than is provided by TL-MCTAG. Scram- bling is one well-known example (Rambow, 1994). In addition, in the semantics domain, the use of a new TAG operation, flexible composition, is used to perform certain semantic operations that seemingly cannot be modeled with TL-MCTAG alone (Chiang and Scheffler, 2008) and in work in synchronous TAG semantics, constructions such as nested quanti- fiers require a set-local MCTAG (SL-MCTAG) anal- ysis (Nesson and Shieber, 2006). In this paper we suggest a shift in focus from constraining locality and complexity through restric- tions that all trees in a tree set must adjoin within a single tree or tree set to constraining locality and complexity through restrictions on the derivational distance between trees in the same tree set in a valid derivation. We examine three formalisms, two of them introduced in this work for the first time, that use derivational distance to constrain locality and demonstrate by construction of parsers their re- lationship to TL-MCTAG in both expressivity and complexity. In Section 2 we give …

Content truncated to 500 words