A Faster Parsing Algorithm for Lexicalized Tree-Adjoining Grammars
Jason M. Eisner, Giorgio Satta · 2000
This paper points out some computational inefficiencies of standard TAG parsing algorithms when applied to LTAGs. We propose a novel algorithm with an asymptotic improvement, from O(n 8 g 2 t) to O(n 6 max(n; g)gt), where n is the input length and g; t are grammar constants that are independent of vocabulary size. Introduction Lexicalized Tree-Adjoining Grammars (LTAGs) were first introduced in (Schabes et al., 1988) as a variant of Tree-Adjoining Grammars (TAGs) (Joshi, 1987). In LTAGs each elementary tree is specialized for some individual lexical item. Following the original proposal, LTAGs have been used in several state-of-the-art, real-world parsers; see for instance (Abeille & Candito, 2000) and (Doran et al., 2000). Like link grammar (Sleator & Temperley, 1991) and lexicalized formalisms from the statistical parsing literature (Collins, 1997; Charniak, 1997; Alshawi, 1996; Eisner, 1996) LTAGs provide two main recognized advantages over more standard non-lexicalized for...