Klein, Dan and Manning, Christopher D. (2001) Parsing and Hypergraphs. In: Seventh International Workshop on Parsing Technologies (IWPT- 2001), October 17-19, 2001, Beijing, China.
This is the latest version of this item.
While symbolic parsers can be viewed as deduction systems, this view is less natural for probabilistic parsers. We present a view of parsing as directed hypergraph analysis which naturally covers both symbolic and probabilistic parsing. We illustrate the approach by showing how a dynamic extension of Dijkstra's algorithm can be used to construct a probabilistic chart parser with an $O(n^3)$ time bound for arbitrary PCFGs, while preserving as much of the flexibility of symbolic chart parsers as allowed by the inherent ordering of probabilistic dependencies.
|Item Type:||Conference or Workshop Item (Paper)|
|Uncontrolled Keywords:||parsing, algorithms, hypergraphs, natural language|
|Related URLs:||Project Homepage||http://www-nlp.stanford.edu/|
|Deposited By:||Import Account|
|Deposited On:||14 Feb 2002 16:00|
|Last Modified:||27 Dec 2008 10:14|
Available Versions of this Item
- An O(n^3) Agenda-Based Chart Parser for Arbitrary Probabilistic Context-Free Grammars. (deposited 26 Apr 2001 17:00)
- Parsing and Hypergraphs. (deposited 14 Feb 2002 16:00) [Currently Displayed]
Repository Staff Only: item control page