HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

On TAG and Multicomponent TAG Parsing

Abstract : The notion of mild context-sensitivity is an attempt to express the formal power needed to define the syntax of natural languages. However, all incarnati- ons of mildly context-sensitive formalisms are not equivalent. On the one hand, near the bottom of the hierarchy, we find tree adjoining grammars and, on the other hand, near the top of the hierarchy, we find multicomponent tree adjoining grammars. This paper proposes a polynomial parse time method for these two tree rewriting formalisms. This method uses range concatenation grammars as a high-level intermediate definition formalism, and yields several algorithms. Range concatenation grammar is a syntactic formalism which is both powerful, in so far as it extends linear context-free rewriting systems, and efficient, in so far as its sentences can be parsed in polynomial time. We show that any unrestricted tree adjoining grammar can be transformed into an equivalent range concatenation grammar which can be parsed in O(n6) time, and, moreover, if the input tree adjoining grammar has some restricted form, its parse time decreases to O(n5). We generalize one of these algorithms in order to process multicomponent tree adjoining grammars. We show some upper bounds on their parse times, and we introduce a hierarchy of restricted forms which can be parsed more efficiently. Our approach aims at giving both a new insight into the multicomponent adjunction mechanism and at providing a practical implementation scheme.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 11:34:10 AM
Last modification on : Friday, February 4, 2022 - 3:09:57 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:35:14 PM


  • HAL Id : inria-00073004, version 1



Pierre Boullier. On TAG and Multicomponent TAG Parsing. [Research Report] RR-3668, INRIA. 1999. ⟨inria-00073004⟩



Record views


Files downloads