On Computing Best Trees forWeighted Tree Automata
2016 (English)In: Proc. 4th Intl. Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016) / [ed] A. Maletti, 2016Conference paper (Refereed)
We propose an algorithm for computing the $N$ best roots of a weighted hypergraph, in which the weight function is given over an idempotent and multiplicatively monotone semiring. We give a set of conditions that ensures that the weight function is well-defined and that solutions exist. Under these conditions, we prove that the proposed algorithm is correct. This generalizes a previous result for weighted tree automata, and in doing so, broadens the practical applications.
Place, publisher, year, edition, pages
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-122474OAI: oai:DiVA.org:umu-122474DiVA: diva2:939172
Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016)