{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:45:56Z","timestamp":1725860756600},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319409450"},{"type":"electronic","value":"9783319409467"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40946-7_4","type":"book-chapter","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T11:52:20Z","timestamp":1467719540000},"page":"39-50","source":"Crossref","is-referenced-by-count":0,"title":["Computing the Expected Edit Distance from a String to a PFA"],"prefix":"10.1007","author":[{"given":"Jorge","family":"Calvo-Zaragoza","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Colin","family":"de la Higuera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jose","family":"Oncina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,6]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.patrec.2013.09.014","volume":"36","author":"J Abreu","year":"2014","unstructured":"Abreu, J., Rico-Juan, J.R.: A new iterative algorithm for computing a quality approximate median of strings based on edit operations. Patt. Rec. Lett. 36, 74\u201380 (2014)","journal-title":"Patt. Rec. Lett."},{"unstructured":"Allauzen, C., Mohri, M.: Linear-Space Computation of the Edit-Distance Between a String and a Finite Automaton (2009). CoRR abs\/0904.4686","key":"4_CR2"},{"unstructured":"Balle, B.: Learning finite-state machines: algorithmic and statistical aspects. Ph.D. thesis, Universitat Polit\u00e9cnica de Catalunya (2013)","key":"4_CR3"},{"key":"4_CR4","first-page":"1841","volume":"9","author":"L Becerra-Bonache","year":"2008","unstructured":"Becerra-Bonache, L., de la Higuera, C., Janodet, J.C., Tantini, F.: Learning balls of strings from edit corrections. J. Mach. Learn. Res. 9, 1841\u20131870 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"4_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-73235-5","volume-title":"Rational Series and Their Languages","author":"J Berstel","year":"1988","unstructured":"Berstel, J., Reutenauer, C.: Rational Series and Their Languages. Springer, Heidelberg (1988)"},{"unstructured":"Calvo-Zaragoza, J., de la Higuera, C., Oncina, J.: Computing the expected edit distance from a string to a PFA. Complete Version with Appendices (2016). https:\/\/hal.archives-ouvertes.fr\/hal-01308549","key":"4_CR6"},{"key":"4_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probalistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin, R., Eddy, S., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probalistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)"},{"doi-asserted-by":"crossref","unstructured":"Ehling, N., Zens, R., Ney, H.: Minimum Bayes risk decoding for BLEU. In: Proceedings of 45th Annual Meeting of the Association for Computational Linguistics (ACL) (2007)","key":"4_CR8","DOI":"10.3115\/1557769.1557799"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0304-3975(97)00240-5","volume":"230","author":"C Higuera de la","year":"2000","unstructured":"de la Higuera, C., Casacuberta, F.: Topology of strings: median string is NP-complete. Theor. Comput. Sci. 230, 39\u201348 (2000)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"de la Higuera, C., Oncina, J.: Computing the most probable string with a probabilistic finite state machine. In: Proceedings of FSMNLP (2013)","key":"4_CR10","DOI":"10.1093\/logcom\/exs049"},{"issue":"2","key":"4_CR11","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1093\/logcom\/exs049","volume":"24","author":"C Higuera de la","year":"2014","unstructured":"de la Higuera, C., Oncina, J.: The most probable string: an algorithmic study. J. Logic Comput. 24(2), 311\u2013330 (2014)","journal-title":"J. Logic Comput."},{"key":"4_CR12","volume-title":"Statistical Methods for Speech Recognition","author":"F Jelinek","year":"1997","unstructured":"Jelinek, F.: Statistical Methods for Speech Recognition. MIT Press, Cambridge (1997)"},{"issue":"2","key":"4_CR13","first-page":"331","volume":"14","author":"F Kruzslicz","year":"1999","unstructured":"Kruzslicz, F.: Improved greedy algorithm for computing approximate median strings. Acta Cybernetica 14(2), 331\u2013339 (1999)","journal-title":"Acta Cybernetica"},{"issue":"4","key":"4_CR14","first-page":"845","volume":"163","author":"VI Levenshtein","year":"1965","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Dokl. Akad. Nauk SSSR 163(4), 845\u2013848 (1965)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"1\u20133","key":"4_CR15","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0167-8655(02)00209-X","volume":"24","author":"CD Mart\u00ednez-Hinarejos","year":"2003","unstructured":"Mart\u00ednez-Hinarejos, C.D., Juan, A., Casacuberta, F.: Median strings for k-nearest neighbour classification. Pattern Rec. Lett. 24(1\u20133), 173\u2013181 (2003)","journal-title":"Pattern Rec. Lett."},{"issue":"4","key":"4_CR16","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1162\/0891201042544938","volume":"30","author":"S Mihov","year":"2004","unstructured":"Mihov, S., Schulz, K.U.: Fast approximate search in large dictionaries. Comput. Linguist. 30(4), 451\u2013477 (2004)","journal-title":"Comput. Linguist."},{"issue":"6","key":"4_CR17","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1142\/S0129054103002114","volume":"14","author":"M Mohri","year":"2003","unstructured":"Mohri, M.: Edit-distance of weighted automata: general definitions and algorithms. Int. J. Found. Comput. Sci. 14(6), 957\u2013982 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithm","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithm. Springer, Berlin (1995)"},{"key":"4_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316135228","volume-title":"Flexible Pattern Matching","author":"G Navarro","year":"2002","unstructured":"Navarro, G., Raffinot, M.: Flexible Pattern Matching. Cambridge University Press, Cambridge (2002)"},{"key":"4_CR20","volume-title":"Introduction to Probabilistic Automata","author":"A Paz","year":"1971","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)"},{"issue":"5","key":"4_CR21","doi-asserted-by":"crossref","first-page":"1103","DOI":"10.1109\/TASL.2010.2091635","volume":"19","author":"R Schluter","year":"2011","unstructured":"Schluter, R., Nussbaum-Thom, M., Ney, H.: On the relationship between Bayes risk and word error rate in ASR. IEEE Trans. Audio Speech Lang. Process. 19(5), 1103\u20131112 (2011)","journal-title":"IEEE Trans. Audio Speech Lang. Process."},{"issue":"2","key":"4_CR22","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1109\/TPAMI.2011.163","volume":"34","author":"R Schluter","year":"2012","unstructured":"Schluter, R., Nussbaum-Thom, M., Ney, H.: Does the cost function matter in Bayes decision rule? IEEE Trans. Pattern Anal. Mach. Intell. 34(2), 292\u2013301 (2012)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"4_CR23","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s10032-002-0082-8","volume":"5","author":"KU Schulz","year":"2002","unstructured":"Schulz, K.U., Mihov, S.: Fast string correction with Levenshtein automata. IJDAR 5(1), 67\u201385 (2002)","journal-title":"IJDAR"},{"doi-asserted-by":"crossref","unstructured":"Stolcke, A., Konig, Y., Weintraub, M.: Explicit word error minimization in n-best list rescoring. In: 5th European Conference on Speech Communication and Technology (1997)","key":"4_CR24","DOI":"10.21437\/Eurospeech.1997-68"},{"issue":"11","key":"4_CR25","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L Valiant","year":"1984","unstructured":"Valiant, L.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"4_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2003","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2003)"},{"issue":"7","key":"4_CR27","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1109\/TPAMI.2005.147","volume":"27","author":"E Vidal","year":"2005","unstructured":"Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., Carrasco, R.C.: Probabilistic finite state automata - part I and II. Pattern Anal. Mach. Intell. 27(7), 1013\u20131039 (2005)","journal-title":"Pattern Anal. Mach. Intell."},{"issue":"5","key":"4_CR28","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1145\/360980.360995","volume":"17","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A.: Order- $$n$$ correction for regular languages. Commun. ACM 17(5), 265\u2013268 (1974)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40946-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T03:56:33Z","timestamp":1692417393000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40946-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319409450","9783319409467"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40946-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}