An efficient best-trees algorithm for weighted tree automata over the tropical semiring
2015 (English)In: Proc. 9th International Conference on Language and Automata Theory and Applications / [ed] Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, and Bianca Truthe, Springer, 2015, 97-108 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Springer, 2015. 97-108 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 8977
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-96680DOI: 10.1007/978-3-319-15579-1_7OAI: oai:DiVA.org:umu-96680DiVA: diva2:766062
9th International Conference on Language and Automata Theory and Applications, LATA 2015, Nice, France, March 2-6, 2015
ProjectsMICO: Media in Context
FunderEU, FP7, Seventh Framework Programme, 610480