Advertisement
Published in:
2015 | OriginalPaper | Chapter
An Efficient Best-Trees Algorithm for Weighted Tree Automata over the Tropical Semiring
Authors : Johanna Björklund, Frank Drewes, Niklas Zechner
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We generalise a search algorithm by Mohri and Riley from strings to trees. The original algorithm takes as input a weighted automaton
$$M$$
over the tropical semiring, together with an integer
$$N$$
, and outputs
$$N$$
strings of minimal weight with respect to
$$M$$
. In our setting,
$$M$$
defines a weighted tree language, again over the tropical semiring, and the output is a set of
$$N$$
trees with minimal weight. 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$$
.