{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T18:28:53Z","timestamp":1769020133820,"version":"3.49.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319948119","type":"print"},{"value":"9783319948126","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94812-6_5","type":"book-chapter","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T22:12:26Z","timestamp":1530223946000},"page":"46-58","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Algorithms for Weighted Finite Automata with Failure Transitions"],"prefix":"10.1007","author":[{"given":"Cyril","family":"Allauzen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael D.","family":"Riley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"issue":"6","key":"5_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"5_CR2","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/978-3-642-01492-5_11","volume-title":"Handbook of Weighted Automata","author":"J Albert","year":"2009","unstructured":"Albert, J., Kari, J.: Digital image compression. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series, pp. 453\u2013479. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_11"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Allauzen, C., Mohri, M., Roark, B.: Generalized algorithms for constructing language models. In: Proceedings of ACL, pp. 40\u201347 (2003)","DOI":"10.3115\/1075096.1075102"},{"key":"5_CR4","unstructured":"Allauzen, C., Riley, M.: SFST: Stochastic FST Library (2017). http:\/\/sfst.opengrm.org"},{"key":"5_CR5","doi-asserted-by":"publisher","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)"},{"key":"5_CR6","unstructured":"Bj\u00f6rklund, H., Bj\u00f6rklund, J., Zechner, N.: Compact representation of finite automata with failure transitions. Technical report, UMINF 13.11, Ume\u00e5 University (2013)"},{"key":"5_CR7","unstructured":"Breuel, T.M.: The OCRopus open source OCR system. In: Proceedings of IS&T\/SPIE 20th Annual Symposium (2008)"},{"key":"5_CR8","unstructured":"Chen, S., Goodman, J.: An empirical study of smoothing techniques for language modeling. Technical report, TR-10-98, Harvard University (1998)"},{"key":"5_CR9","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. MITP (1992)"},{"key":"5_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.J.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, London (1998)"},{"issue":"3","key":"5_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1017\/S1351324914000175","volume":"21","author":"P Ebden","year":"2015","unstructured":"Ebden, P., Sproat, R.: The Kestrel TTS text normalization system. Nat. Lang. Eng. 21(3), 333\u2013353 (2015)","journal-title":"Nat. Lang. Eng."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Hellsten, L., Roark, B., Goyal, P., Allauzen, C., Beaufays, F., Ouyang, T., Riley, M., Rybach, D.: Transliterated mobile keyboard input via weighted finite-state transducers. In: FSMNLP 2017, pp. 10\u201319 (2017)","DOI":"10.18653\/v1\/W17-4002"},{"key":"5_CR13","unstructured":"Iglesias, G., Allauzen, C., Byrne, W., de Gispert, A., Riley, M.: Hierarchical phrase-based translation representations. In: EMNLP 2011, pp. 1373\u20131383 (2011)"},{"issue":"3","key":"5_CR14","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1109\/TASSP.1987.1165125","volume":"35","author":"SM Katz","year":"1987","unstructured":"Katz, S.M.: Estimation of probabilities from sparse data for the language model component of a speech recogniser. IEEE Trans. Acoust. Speech Signal Process. 35(3), 400\u2013401 (1987)","journal-title":"IEEE Trans. Acoust. Speech Signal Process."},{"key":"5_CR15","unstructured":"Kourie, D.G., Watson, B.W., Cleophas, L.G., Venter, F.: Failure deterministic finite automata. In: Stringology, pp. 28\u201341 (2012)"},{"issue":"2","key":"5_CR16","first-page":"217","volume":"4","author":"M Mohri","year":"1997","unstructured":"Mohri, M.: String-matching with automata. Nord. J. Comput. 4(2), 217\u2013231 (1997)","journal-title":"Nord. J. Comput."},{"issue":"3","key":"5_CR17","first-page":"321","volume":"7","author":"M Mohri","year":"2002","unstructured":"Mohri, M.: Semiring frameworks and algorithms for shortest-distance problems. J. Automata Lang. Comb. 7(3), 321\u2013350 (2002)","journal-title":"J. Automata Lang. Comb."},{"key":"5_CR18","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-01492-5_6","volume-title":"Handbook of Weighted Automata","author":"M Mohri","year":"2009","unstructured":"Mohri, M.: Weighted automata algorithms. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series, pp. 213\u2013254. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_6"},{"key":"5_CR19","series-title":"Springer Handbooks","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-540-49127-9_28","volume-title":"Springer Handbook of Speech Processing","author":"M Mohri","year":"2008","unstructured":"Mohri, M., Pereira, F., Riley, M.: Speech recognition with weighted finite-state transducers. In: Benesty, J., Sondhi, M.M., Huang, Y.A. (eds.) Springer Handbook of Speech Processing. SH, pp. 559\u2013584. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-49127-9_28"},{"key":"5_CR20","unstructured":"Mohri, M., Yang, S.: Competing with automata-based expert sequences. In: Proceedings of AISTATS (2018)"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Novak, J.R., Minematsu, N., Hirose, K.: Failure transitions for joint n-gram models and G2P conversion. In: INTERSPEECH, pp. 1821\u20131825 (2013)","DOI":"10.21437\/Interspeech.2013-449"},{"issue":"1","key":"5_CR22","first-page":"43","volume":"29","author":"M Nxumalo","year":"2017","unstructured":"Nxumalo, M., Kourie, D.G., Cleophas, L., Watson, B.W.: An assessment of algorithms for deriving failure deterministic finite automata. S. Afr. Comput. J. 29(1), 43\u201368 (2017)","journal-title":"S. Afr. Comput. J."},{"key":"5_CR23","unstructured":"Roark, B., Allauzen, C., Riley, M.: Smoothed marginal distribution constraints for language modeling. In: ACL 2013, vol. 1, pp. 43\u201352 (2013)"},{"key":"5_CR24","volume-title":"Principles of Mathematical Analysis","author":"W Rudin","year":"1964","unstructured":"Rudin, W.: Principles of Mathematical Analysis, vol. 3. McGraw-Hill, New York (1964)"},{"key":"5_CR25","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-642-01492-5_4","volume-title":"Handbook of Weighted Automata","author":"J Sakarovich","year":"2009","unstructured":"Sakarovich, J.: Rational and recognizable power series. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series, pp. 105\u2013174. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_4"},{"issue":"1","key":"5_CR26","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1080\/00029890.1981.11995179","volume":"88","author":"P Schaefer","year":"1981","unstructured":"Schaefer, P.: Sum-preserving rearrangements of infinite series. Am. Math. Monthly 88(1), 33\u201340 (1981)","journal-title":"Am. Math. Monthly"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Velikovich, L.: Semantic model for fast tagging of word lattices. In: 2016 IEEE Spoken Language Technology Workshop (SLT), pp. 398\u2013405. IEEE (2016)","DOI":"10.1109\/SLT.2016.7846295"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94812-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:45:24Z","timestamp":1709826324000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94812-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319948119","9783319948126"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94812-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Charlottetown, PE","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.smcs.upei.ca\/ciaa2018","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}