Tree insertion grammar: a cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced
Yves Schabes, Richard C. Waters · 1995
Tree insertion grammar (TIG) is a tree-based formalism that makes use of tree substitution and tree adjunction. TIG is related to tree adjoining grammar. However, the adjunction permitted in TIG is sufficiently restricted that TIGs only derive context free languages and TIGs have the same cubic-time worst-case complexity bounds for recognition and parsing as context free grammars. An efficient Earley-style parser for TIGs is presented. Any