Name
Abstract | ||
|---|---|---|
We generalise a search algorithm by Mohri and Riley from strings to trees. The original algorithm takes as input a nondeterministic weighted automaton M over the tropical semiring and an integer N, and outputs N strings of minimal weight with respect to M. In our setting, M is a weighted tree automaton, again over the tropical semiring, and the output is a set of N trees with minimal weight in this language. We prove that the algorithm is correct, and that its time complexity is a low polynomial in N and the relevant size parameters of M. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.jcss.2017.03.006 | Journal of Computer and System Sciences |
Keywords | Field | DocType |
Weighted tree automaton,N-best analysis,Tropical semiring | Integer,Discrete mathematics,Combinatorics,Search algorithm,Nondeterministic algorithm,Enumeration,Automaton,Noncommutative signal-flow graph,Mathematics,Semiring | Journal |
Volume | ISSN | Citations |
104 | 0022-0000 | 0 |
PageRank | References | Authors |
0.34 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johanna Björklund | 1 | 5 | 6.23 |
| Frank Drewes | 2 | 26 | 6.10 |
| Niklas Zechner | 3 | 3 | 3.19 |