Publications:
All
 de la Higuera, C.; Oncina, J.
"Finding the most probable string and the consensus string: an algorithmic study" In: 12th International Conference on Parsing Technologies (IWPT 2011), pp. 2636, Dublin
(2011)
: bibtex
: pdfAbstract: The problem of finding the most probable string for a distribution generated by a weighted finite automaton 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 $\NP$hard if the automaton is probabilistic. In this paper we give a pseudopolynomial algorithm which computes the most probable string in time polynomial in the inverse of the probability of this string itself. We also give a randomised algorithm solving the same problem and discuss the case where the distribution is generated by other types of machines.
@inproceedings {
author = "de la Higuera, C.; Oncina, J.",
title = "Finding the most probable string and the consensus string: an algorithmic study",
address = "Dublin",
booktitle = "In: 12th International Conference on Parsing Technologies (IWPT 2011)",
month = "October ",
pages = "2636",
year = "2011"
}
