Weighted Deductive Parsing and Knuth's Algorithm
Bibliographic Data
| ID | 12156372 |
|---|---|
| Authors | Mark-Jan Nederhof (0000-0002-1845-6829, Faculty of Arts, Humanities Computing, University of Groningen, P.O. Box 716, NL-9700 AS Groningen, The Netherlands. Secondary affiliation is the German Research Center for Artificial Intelligence (DFKI)., corresponding author) |
| Year | 2003 |
| Volume | 29 |
| Issue | 1 |
| Pages | 135-143 |
| Publication date | 2003-03-01 |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Computational Linguistics (JOURNAL) |
| Journal identifiers | ISSN: 0891-2017 • E-ISSN: 1530-9312 |
| Publisher | Association for Computational Linguistics (PUBLISHER • US) |
| DOI | 10.1162/089120103321337467 |
| OpenAlex | W2115753373 |
| Language | EN |
| Citations received | 6 |
| References cited | 10 |
We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system
Algorithm · Dijkstra's algorithm · Generalization · Graph · Modular design · Parsing · Path (computing · Programming language · Shortest path problem · Algorithms and Data Compression · Computer Science · DNA and Biological Computing · Mathematics · semigroups and automata theory · Artificial Intelligence · Theoretical Computer Science
Linear Context‐Free Rewriting Systems
Grammar Factorization by Tree Decomposition
Binarization of Synchronous Context-Free Grammars
Efficient Outside Computation
Phrase Dependency Machine Translation with Quasi-Synchronous Tree-to-Tree Features
Data-Driven Parsing using Probabilistic Linear Context-Free Rewriting Systems
| Citations per year | 0.35 |
|---|---|
| Citation span | 2009 - 2020 (12) |
| Highly cited | No |