Finding the most probable string and the consensus string: an algorithmic study
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/23421
Título: | Finding the most probable string and the consensus string: an algorithmic study |
---|---|
Autor/es: | Higuera, Colin de la | Oncina, Jose |
Grupo/s de investigación o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Palabras clave: | Most probable string | Probabilistic finite automata | Polynomial algorithm |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos |
Fecha de publicación: | oct-2011 |
Resumen: | 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. |
Descripción: | Paper submited to IWPT 2011, 12th International Conference on Parsing Technologies, Dublin, Ireland, October 5-7, 2011. |
Patrocinador/es: | Spanish CICyT through projects TIN2009-14205-C04-C1, and the program CONSOLIDER INGENIO 2010 (CSD2007-00018). |
URI: | http://hdl.handle.net/10045/23421 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/conferenceObject |
Revisión científica: | si |
Aparece en las colecciones: | INV - GRFIA - Comunicaciones a Congresos, Conferencias, etc. |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
iwpt2011.pdf | 150,57 kB | Adobe PDF | Abrir Vista previa | |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.