Name
Abstract | ||
|---|---|---|
We propose an algorithm for computing the N best vertices in a weighted acyclic hypergraph over a nice semiring. A semiring is nice if it is finitely-generated, idempotent, and has 1 as its minimal element. We then apply the algorithm to the problem of computing the N best trees with respect to a weighted tree automaton, and complement theoretical correctness and complexity arguments with experimental data. The algorithm has several practical applications in natural language processing, for example, to derive the N most likely parse trees with respect to a probabilistic context-free grammar. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2017.03.010 | Theoretical Computer Science |
Keywords | Field | DocType |
Hypergraph,N-best problem,Idempotent semiring | Discrete mathematics,Combinatorics,Vertex (geometry),Hypergraph,Idempotence,Mathematics,Semiring | Journal |
Volume | ISSN | Citations |
682 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johanna Björklund | 1 | 5 | 6.23 |
| Frank Drewes | 2 | 26 | 6.10 |
| Anna Jonsson | 3 | 0 | 0.34 |