On Multicomponent TAG Parsing
Pierre Boullier
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 incarnations 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 multicomponent tree adjoining grammars. This method uses range concatenation grammars as a high-level intermediate definition formalism. We show some upper bounds on the parse time of the set-local version of multicomponent tree adjoining grammar, 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 schema.