Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

By Jason Eisner, Giorgio Satta. 1999

Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n4) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of O(n5). For a common special case that was known to allow O(n3) parsing (Eisner, 1997), we present an O(n3) algorithm with an improved grammar constant.

Subfields: Information Extraction, Computational Linguistics & Semantics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Extraction

In Computational Linguistics & Semantics

Citations in the corpus

The Right Tool for the Job: Matching Model and Instance Complexities (2020, background): “Methods for making inference more efﬁcient have received considerable attention in NLP over the years (Eisner and Satta, 1999; Goldberg and El-hadad, 2010, inter alia ).”
Accurate Unlexicalized Parsing (2003, methodology): “6 The parser is available for download as open source at: http://nlp.stanford.edu/downloads/lex-parser.shtml”
Head-Driven Statistical Models for Natural Language Parsing (2003, methodology): “Eisner and Satta (1999) also describe an O(n3) algorithm for a restricted class of lexicalized grammars; it is an open question whether this restricted class includes the models in this article.”
Fast Exact Inference with a Factored Model for Natural Language Parsing (2002, methodology): “For the semantic model, P(D), there are several presentations of cubic dependency parsi ng algorithms, including [9] and [12].”
Online Large-Margin Training of Dependency Parsers (2005, background): “Eisner and Satta (1999) give a cubic algorithm for lexicalized phrase structures.”
Dependency Parsing by Belief Propagation (2008, methodology): “The runtime of summing over all assignments A in 11 For example, with unknown tags T , a model with PT REE +T AG L INK will take only O ( n 3 + n 2 g 2 ) time for BP, compared to O ( n 3 g 2 ) time for dynamic programming (Eisner & Satta 1999).”
Probabilistic Top-Down Parsing and Language Modeling (2001, background): “Examples of this are bilexical grammars – see e.g. Eisner and Satta (1999), Charniak (1997), Collins (1997) – where the lexical heads of each constituent are annotated on both the right- and left-hand sides of the context free rules, under the constraint that every constituent inherits the lexical…”