| Título: | The most probable string: an algorithmic study |
| Autores: |
Higuera, Colin de la Oncina Carratalá, Jose |
| Fecha: |
2013-07-09 2013-07-09 2013-01-17 |
| Publicador: | RUA Docencia |
| Fuente: |
 |
| Tipo: | info:eu-repo/semantics/article |
| Tema: |
Probabilistic automata Parsing Lenguajes y Sistemas Informáticos |
| Descripción: |
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. The first author acknowledges partial support by the Région des Pays de la Loire. The second author thanks the Spanish CICyT for partial support of this work through projects TIN2009-14205-C04-C1, and the program Consolider Ingenio 2010 (CSD2007-00018). This work was supported in part by the IST Programme of the European Community, under the Pascal 2 Network of Excellence, IST-2007-216886. |
| Idioma: | Inglés |
1 Choosing the correct paradigm for unknown words in rule-based machine translation systems por Sánchez Cartagena, Víctor Manuel,Esplà Gomis, Miquel,Sánchez Martínez, Felipe,Pérez Ortiz, Juan Antonio | 6 Análisis Real de Varias Variables II. Problemas (27-3-2013) por Conde Calero, Juan Manuel |
2 Using external sources of bilingual information for on-the-fly word alignment por Esplà Gomis, Miquel,Sánchez Martínez, Felipe,Forcada Zubizarreta, Mikel L. | 7 Introducción a mirada/s trans/identitarias,Introduction to trans-identitary look(s) por Amaro Quintas, Ángel Manuel |
3 | 8 |
4 | 9 |
5 Los espacios periurbanos en el área ibérica contestana: las novedades y algunas reflexiones históricas por Sala Sellés, Feliciana | 10 Matrimonio igualitario y parentesco: discursos, hegemonías y acontecimiento,Egalitarian marriage and kinship: discourses, hegemony and event por Buzaglo, Analía,Morandi, Mariela,Culla, Mónica |