Show simple item record

dc.contributor.authorNesson, Rebecca
dc.contributor.authorShieber, Stuart M.
dc.contributor.authorSatta, Giorgio
dc.date.accessioned2011-02-24T18:24:03Z
dc.date.issued2010
dc.identifier.citationNesson, Rebecca, Stuart M. Shieber, and Giorgio Satta. 2010. Complexity, parsing, and factorization of tree-local multi-component tree-adjoining grammar. Computational Linguistics 36(3): 443-480.en_US
dc.identifier.issn0891-2017en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:4731603
dc.description.abstractTree-Local Multi-Component Tree-Adjoining Grammar (TL-MCTAG) is an appealing formalism for natural language representation because it arguably allows the encapsulation of the appropriate domain of locality within its elementary structures. Its multicomponent structure allows modeling of lexical items that may ultimately have elements far apart in a sentence, such as quantifiers and Wh-words. When used as the base formalism for a synchronous grammar, its flexibility allows it to express both the close relationships and the divergent structure necessary to capture the links between the syntax and semantics of a single language or the syntax of two different languages. Its limited expressivity provides constraints on movement and, we posit, may have generated additional popularity based on a misconception about its parsing complexity. Although TL-MCTAG was shown to be equivalent in expressivity to TAG when it was first introduced (Weir 1988), the complexity of TL-MCTAG is still not well-understood. This paper offers a thorough examination of the problem of TL-MCTAG recognition, showing that even highly restricted forms of TL-MCTAG are NP-complete to recognize. However, in spite of the provable difficulty of the recognition problem, we offer several algorithms that can substantially improve processing efficiency. First, we present a parsing algorithm that improves on the baseline parsing method and runs in polynomial time when both the fan-out and rank of the input grammar are bounded. Second, we offer an optimal, efficient algorithm for factorizing a grammar to produce a strongly-equivalent TL-MCTAG grammar with the rank of the grammar minimized.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherMassachusetts Institute of Technology Press (MIT Press)en_US
dc.relation.isversionofdoi:10.1162/coli_a_00005en_US
dash.licenseOAP
dc.titleComplexity, Parsing, and Factorization of Tree-Local Multi-Component Tree-Adjoining Grammaren_US
dc.typeJournal Articleen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalComputational Linguisticsen_US
dash.depositing.authorShieber, Stuart M.
dc.date.available2011-02-24T18:24:03Z
dc.identifier.doi10.1162/coli_a_00005*
dash.identifier.orcid0000-0002-7733-8195*
dash.contributor.affiliatedShieber, Stuart


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record