Efficient enumeration of weighted tree languages over the rropical semiring
2017 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, , 78 p.Article in journal (Refereed) Epub ahead of print
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.
Place, publisher, year, edition, pages
2017. , 78 p.
weighted tree automaton, N-best analysis, tropical semiring
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-132963DOI: 10.1016/j.jcss.2017.03.006OAI: oai:DiVA.org:umu-132963DiVA: diva2:1084722