{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T16:52:14Z","timestamp":1648831934868},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p> In a number of fields, it is necessary to compare a witness string with a distribution. One possibility is to compute the probability of the string for that distribution. Another, giving a more global view, is to compute the expected edit distance from a string randomly drawn to the witness string. This number is often used to measure the performance of a prediction, the goal then being to return the median string, or the string with smallest expected distance. To be able to measure this, computing the distance between a hypothesis and that distribution is necessary. This paper proposes two solutions for computing this value, when the distribution is defined with a probabilistic finite state automaton. The first is exact but has a cost which can be exponential in the length of the input string, whereas the second is a fully polynomial-time randomized schema. <\/jats:p>","DOI":"10.1142\/s0129054117400093","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T08:31:43Z","timestamp":1513326703000},"page":"603-621","source":"Crossref","is-referenced-by-count":3,"title":["Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton"],"prefix":"10.1142","volume":"28","author":[{"given":"Jorge","family":"Calvo-Zaragoza","sequence":"first","affiliation":[{"name":"Department of Software and Computing Systems, University of Alicante, Carretera de San Vicente s\/n, Alicante, Spain"}]},{"given":"Jose","family":"Oncina","sequence":"additional","affiliation":[{"name":"Department of Software and Computing Systems, University of Alicante, Carretera de San Vicente s\/n, Alicante, Spain"}]},{"given":"Colin","family":"de la Higuera","sequence":"additional","affiliation":[{"name":"Laboratoire d\u2019Informatique de Nantes-Atlantique, University of Nantes, UMR 6241, Nantes, France"}]}],"member":"219","published-online":{"date-parts":[[2017,12,15]]},"reference":[{"key":"S0129054117400093BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2013.09.014"},{"key":"S0129054117400093BIB004","first-page":"1841","volume":"9","author":"Becerra-Bonache L.","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"S0129054117400093BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-73235-5"},{"key":"S0129054117400093BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00240-5"},{"key":"S0129054117400093BIB009","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exs049"},{"key":"S0129054117400093BIB010","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492"},{"key":"S0129054117400093BIB012","volume-title":"Statistical Methods for Speech Recognition","author":"Jelinek F.","year":"1997"},{"issue":"4","key":"S0129054117400093BIB014","first-page":"845","volume":"163","author":"Levenshtein V. I.","year":"1965","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0129054117400093BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(02)00209-X"},{"key":"S0129054117400093BIB016","doi-asserted-by":"publisher","DOI":"10.1162\/0891201042544938"},{"key":"S0129054117400093BIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002114"},{"key":"S0129054117400093BIB018","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"S0129054117400093BIB019","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316135228"},{"key":"S0129054117400093BIB020","volume-title":"Introduction to Probabilistic Automata","author":"Paz A.","year":"1971"},{"key":"S0129054117400093BIB022","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.163"},{"key":"S0129054117400093BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/s10032-002-0082-8"},{"key":"S0129054117400093BIB025","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"S0129054117400093BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7"},{"key":"S0129054117400093BIB027","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.147"},{"key":"S0129054117400093BIB028","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.147"},{"key":"S0129054117400093BIB029","doi-asserted-by":"publisher","DOI":"10.1145\/360980.360995"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117400093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:20:29Z","timestamp":1565194829000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117400093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":21,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,12,15]]},"published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1142\/S0129054117400093"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117400093","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}