Stanford InfoLab Publication Server

Parsing and Hypergraphs

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
Subjects:Computer Science
Related URLs:Project Homepage
ID Code:729
Deposited By:Import Account
Deposited On:14 Feb 2002 16:00
Last Modified:27 Dec 2008 10:14

Available Versions of this Item

Download statistics

Repository Staff Only: item control page