Publications:
All
 de la Higuera, C.; Oncina, J.
"The most probable string: an algorithmic study " Journal of Logic and Computation, vol. 24, pp. 311330
(2014)
: bibtex
: pdfAbstract: The problem of finding the consensus (most probable string) for a distribution generated by a weighted finite automaton or a probabilistic grammar is related to a number of important questions: computing the distance between two distributions or finding the best translation (the most probable one) given a probabilistic finite state transducer. The problem is undecidable
with general weights and is NPhard if the automaton is probabilistic. We give a pseudopolynomial algorithm that solves a decision problem directly associated with the consensus string and answers if there is a (reasonably short) string whose probability is larger than a given bound in time polynomial in the the size of this bound, both for probabilistic finite automata
and probabilistic contextfree grammars.We also study a randomized algorithm solving the same problem. Finally, we report links between the length of the consensus string and the probability of this string.
@article {
author = "de la Higuera, C.; Oncina, J.",
title = "The most probable string: an algorithmic study ",
issn = "0955792X",
journal = "Journal of Logic and Computation",
number = "2",
pages = "311330",
volume = "24",
year = "2014"
}
