+ 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



  1. de la Higuera, C.; Oncina, J.
    "The most probable string: an algorithmic study "
    Journal of Logic and Computation, vol. 24, pp. 311-330 (2014)
    : bibtex : pdf

    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 NP-hard if the automaton is probabilistic. We give a pseudo-polynomial 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 context-free 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 = "0955-792X",
 journal = "Journal of Logic and Computation",
 number = "2",
 pages = "311-330",
 volume = "24",
 year = "2014"
Valid XHTML 1.0!Valid CSS!