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.
| BibTeX | DublinCore | EndNote | HTML |
This is the latest version of this item.
![[img]](/style/images/fileicons/application_pdf.png)
| PDF 140Kb |
Abstract
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 | |
| Projects: | Miscellaneous | |
| Related URLs: | Project Homepage | http://www-nlp.stanford.edu/ |
| 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
- 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]
Download statistics
Repository Staff Only: item control page
