On the complexity of variants of the k Best strings problem
2010 (English)In: Proceedings of the Prague stringology conference 2010, dblp , 2010, 76-88 p.Conference paper (Refereed)
We investigate the problem of extracting the k best strings from a nondeterministic weighted automaton over a semiring S. This problem, which has been considered earlier in the literature, is more difficult than extracting the k best runs, since distinct runs may not correspond to distinct strings. Unsurprisingly, the computational complexity of the problem depends on the semiring S used. We study three different cases, namely the tropical and complex tropical semirings, and the semiring of positive real numbers. For the first case, we establish a polynomial algorithm. For the second and third cases, NP-completeness and undecidability results are shown.
Place, publisher, year, edition, pages
dblp , 2010. 76-88 p.
Engineering and Technology Algebra and Logic
IdentifiersURN: urn:nbn:se:umu:diva-109058ISI: 000325018000007ISBN: 978-80-01-04597-8OAI: oai:DiVA.org:umu-109058DiVA: diva2:854926
Prague Stringology Conference (PSC), AUG 30-SEP 01, 2010, Czech Tech Univ, Dept Theoret Comp Sci, Prague, CZECH REPUBLIC