Variants of mixed parsing of TAG and TIG
Miguel Ángel Alonso Pardo, Víctor Jesús Díaz Madrigal · 2003
Tree Adjoining Grammar (TAG) is a useful formalism for describing the syntactic structure of natural languages. In practice, a large part of wide coverage TAGs is formed by trees that satisfy the restrictions imposed by Tree Insertion Grammar (TIG), a simpler for- malism. This characteristic can be used to reduce the practical complexity of TAG parsing, applying the standard adjunction operation only in those cases in which the simpler cubic-time TIG adjunction cannot be applied. A major obstacle to this task is posed by the fact that si- multaneous adjunctions are forbidden in TAG but they are allowed in TIG. In this article, we describe several algorithms for mixed parsing of TAG and TIG: a first one forbidding simul- taneous adjunctions, a second one allowing this kind of adjunctions, and a third one which extends the second one to preserve the correct prefix property. RESUME. La Grammaire d'Arbres Adjoints (TAG) est un formalisme utile pour decrire la struc- ture syntaxique des langues naturelles. En pratique, la plupart des TAG a large couverture contiennent des arbres qui satisfont les restrictions imposees par la Grammaire d'Insertion d'Arbres (TIG), qui est un formalisme plus simple. Cette caracteristique peut etre employee pour reduire la complexite pratique de l'analyse TAG, en appliquant l'operation d'adjonction standard seulement dans les cas ou l'adjonction TIG, plus simple, ne peut pas etre appliquee. L'un des plus grands obstacles a cette tâche reside dans le fait que les adjonctions simultanees sont interdites en TAG mais elles sont permises en TIG. Dans cet article, nous decrivons plu- sieurs algorithmes pour l'analyse mixte de TAG et de TIG : 1) celui qui interdit les adjonctions simultanees ; 2) celui qui permet ce type d'adjonction ; et 3) celui qui etend le deuxieme afin de preserver la propriete du prefixe correcte.