Prague Stringology Conference 2010
Martin Berglund and Frank Drewes
On the Complexity of Variants of the k Best Strings Problem
| Abstract: |
| We investigate the problem of extracting the k best strings from a non-deterministic 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |