[grfia]
+ General Information
+ Members
+ Research
+ Intranet

PRAIg '16 / +pics

[]



AERFAI Summer School on Deep Learning

[]

Alicante July 5-6, 2017

10th international workshop on Machine Learning and Music

[]

Barcelona: 16th October 2017

Publications:

All

  1. 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. 26-36, Dublin (2011)
    : bibtex : pdf
    Abstract:

    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 pseudo-polynomial 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 = "26-36",
 year = "2011"
}
Valid XHTML 1.0!Valid CSS!