{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T07:48:06Z","timestamp":1771573686971,"version":"3.50.1"},"publisher-location":"Cham","reference-count":57,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319230207","type":"print"},{"value":"9783319230214","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23021-4_1","type":"book-chapter","created":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T20:47:30Z","timestamp":1441745250000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Learning Weighted Automata"],"prefix":"10.1007","author":[{"given":"Borja","family":"Balle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehryar","family":"Mohri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,9]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Allauzen, C., Mohri, M., Riley, M.: Statistical modeling for unit selection in speech synthesis. In: Proceedings of ACL (2004)","DOI":"10.3115\/1218955.1218963"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Allauzen, C., Mohri, M., Talwalkar, A.: Sequence kernels for predicting protein essentiality. In: Proceedings of ICML (2008)","DOI":"10.1145\/1390156.1390158"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-24372-1_16","volume-title":"Automated Technology for Verification and Analysis","author":"B Aminof","year":"2011","unstructured":"Aminof, B., Kupferman, O., Lampert, R.: Formal analysis of online algorithms. In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol. 6996, pp. 213\u2013227. Springer, Heidelberg (2011)"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D.: On the complexity of minimum inference of regular sets. Information and Control 3(39) (1978)","DOI":"10.1016\/S0019-9958(78)90683-6"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Information and Computation 75(2) (1987)","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"1_CR6","unstructured":"Bailly, R.: M\u00e9thodes spectrales pour l\u2019inf\u00e9rence grammaticale probabiliste de langages stochastiques rationnels. Ph.D. thesis, Aix-Marseille Universit\u00e9 (2011)"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Bailly, R., Denis, F., Ralaivola, L.: Grammatical inference as a principal component analysis problem. In: Proceedings of ICML (2009)","DOI":"10.1145\/1553374.1553379"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Balle, B., Mohri, M.: On the Rademacher complexity of weighted automata. In: Proceedings of ALT (2015)","DOI":"10.1007\/978-3-319-24486-0_12"},{"key":"1_CR9","unstructured":"Balle, B.: Learning Finite-State Machines: Statistical and Algorithmic Aspects. Ph.D. thesis, Universitat Politecnica de Catalunya (2013)"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Balle, B., Carreras, X., Luque, F.M., Quattoni, A.: Spectral learning of weighted automata. Machine Learning 96(1\u20132) (2014)","DOI":"10.1007\/s10994-013-5416-x"},{"key":"1_CR11","unstructured":"Balle, B., Mohri, M.: Spectral learning of general weighted automata via constrained matrix completion. In: Proceedings of NIPS (2012)"},{"key":"1_CR12","unstructured":"Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: On the applications of multiplicity automata in learning. In: Proceeding FOCS (1996)"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. Journal of the ACM 47(3) (2000)","DOI":"10.1145\/337244.337257"},{"key":"1_CR14","series-title":"LNCS","first-page":"54","volume-title":"Algorithms and Complexity CIAC 1994","author":"F Bergadano","year":"1994","unstructured":"Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. In: Bonuccelli, M.A., Crescenzi, P., Petreschi, R. (eds.) CIAC 1994. LNCS, vol. 778, pp. 54\u201362. Springer, Heidelberg (1994)"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. SIAM Journal on Computing 25(6) (1996)","DOI":"10.1137\/S009753979326091X"},{"key":"1_CR16","unstructured":"Berstel, J., Reutenauer, C.: Rational Series and Their Languages. Springer (1988)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/11776420_16","volume-title":"Learning Theory","author":"L Bisht","year":"2006","unstructured":"Bisht, L., Bshouty, N.H., Mazzawi, H.: On optimal learning algorithms for multiplicity automata. In: Lugosi, G., Simon, H.U. (eds.) COLT 2006. LNCS (LNAI), vol. 4005, pp. 184\u2013198. Springer, Heidelberg (2006)"},{"key":"1_CR18","unstructured":"Breuel, T.M.: The OCRopus open source OCR system. In: Proceedings of IS&T\/SPIE (2008)"},{"issue":"4","key":"1_CR19","first-page":"371","volume":"14","author":"A Cardon","year":"1980","unstructured":"Cardon, A., Crochemore, M.: D\u00e9termination de la repr\u00e9sentation standard d\u2019une s\u00e9rie reconnaissable. ITA 14(4), 371\u2013379 (1980)","journal-title":"ITA"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Carlyle, J.W., Paz, A.: Realizations by stochastic finite automata. J. Comput. Syst. Sci. 5(1) (1971)","DOI":"10.1016\/S0022-0000(71)80005-3"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Pre-reduction graph products: Hardnesses of properly learning dfas and approximating edp on dags. In: Proceedings of FOCS (2014)","DOI":"10.1109\/FOCS.2014.54"},{"key":"1_CR22","unstructured":"Cortes, C., Haffner, P., Mohri, M.: Rational kernels: Theory and algorithms. Journal of Machine Learning Research 5 (2004)"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Droste, M., Kuich, W. (eds.): Handbook of weighted automata. EATCS Monographs on Theoretical Computer Science. Springer (2009)","DOI":"10.1007\/978-3-642-01492-5"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Dupont, P., Denis, F., Esposito, Y.: Links between probabilistic automata and hidden markov models: probability distributions, learning models and induction algorithms. Pattern Recognition (2005)","DOI":"10.1016\/j.patcog.2004.03.020"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.J.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press (1998)","DOI":"10.1017\/CBO9780511790492"},{"key":"1_CR26","unstructured":"Eilenberg, S.: Automata, Languages and Machines. Academic Press (1974)"},{"key":"1_CR27","unstructured":"Fazel, M.: Matrix rank minimization with applications. Ph.D. thesis, Stanford University (2002)"},{"key":"1_CR28","unstructured":"Fliess, M.: Matrices de Hankel. Journal de Math\u00e9matiques Pures et Appliqu\u00e9es 53 (1974)"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Information and Control 3(37) (1978)","DOI":"10.1016\/S0019-9958(78)90562-4"},{"key":"1_CR30","unstructured":"Golub, G., Loan, C.V.: Matrix Computations. Johns Hopkins University Press (1983)"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Haussler, D., Littlestone, N., Warmuth, M.K.: Predicting $$\\{0,1\\}$$-functions on randomly drawn points. In: Proceedings of COLT (1988)","DOI":"10.1109\/SFCS.1988.21928"},{"key":"1_CR32","unstructured":"Hsu, D., Kakade, S.M., Zhang, T.: A spectral algorithm for learning hidden markov models. In: Proceedings of COLT (2009)"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"Hsu, D., Kakade, S.M., Zhang, T.: A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences 78(5) (2012)","DOI":"10.1016\/j.jcss.2011.12.025"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"II, K.C., Kari, J.: Image compression using weighted finite automata. Computers & Graphics 17(3) (1993)","DOI":"10.1016\/0097-8493(93)90079-O"},{"key":"1_CR35","unstructured":"Kaplan, R.M., Kay, M.: Regular models of phonological rule systems. Computational Linguistics 20(3) (1994)"},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Karttunen, L.: The replace operator. In: Proceedings of ACL (1995)","DOI":"10.3115\/981658.981661"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Valiant, L.G.: Cryptographic limitations on learning boolean formulae and finite automata. Journal of ACM 41(1) (1994)","DOI":"10.1145\/174644.174647"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press (1994)","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"1_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-662-46678-0_19","volume-title":"Foundations of Software Science and Computation Structures","author":"S Kiefer","year":"2015","unstructured":"Kiefer, S., Marusic, I., Worrell, J.: Minimisation of multiplicity tree automata. In: Pitts, A. (ed.) FOSSACS 2015. LNCS, vol. 9034, pp. 297\u2013311. Springer, Heidelberg (2015)"},{"key":"1_CR40","doi-asserted-by":"crossref","unstructured":"Kuich, W., Salomaa, A.: Semirings, Automata. Springer, Languages (1986)","DOI":"10.1007\/978-3-642-69959-7"},{"key":"1_CR41","unstructured":"Mohri, M.: Finite-state transducers in language and speech processing. Computational Linguistics 23(2) (1997)"},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"Mohri, M.: Weighted automata algorithms. In: Handbook of Weighted Automata. Springer (2009)","DOI":"10.1007\/978-3-642-01492-5_6"},{"key":"1_CR43","unstructured":"Mohri, M., Pereira, F., Riley, M.: Weighted automata in text and speech processing. In: Proceedings of ECAI 1996 Workshop on Extended finite state models of language (1996)"},{"key":"1_CR44","doi-asserted-by":"crossref","unstructured":"Mohri, M., Pereira, F., Riley, M.: Speech recognition with weighted finite-state transducers. In: Handbook on Speech Processing and Speech Comm. Springer (2008)","DOI":"10.1007\/978-3-540-49127-9_28"},{"key":"1_CR45","doi-asserted-by":"crossref","unstructured":"Mohri, M., Pereira, F.C.N.: Dynamic compilation of weighted context-free grammars. In: Proceedings of COLING-ACL (1998)","DOI":"10.3115\/980432.980716"},{"key":"1_CR46","unstructured":"Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of Machine Learning. MIT Press (2012)"},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"Mohri, M., Sproat, R.: An efficient compiler for weighted rewrite rules. In: Proceedings of ACL (1996)","DOI":"10.3115\/981863.981894"},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"Mornhinweg, D., Shapiro, D.B., Valente, K.: The principal axis theorem over arbitrary fields. American Mathematical Monthly (1993)","DOI":"10.2307\/2324781"},{"key":"1_CR49","doi-asserted-by":"crossref","unstructured":"Pereira, F., Riley, M.: Speech recognition by composition of weighted finite automata. In: Finite-State Language Processing. MIT Press (1997)","DOI":"10.7551\/mitpress\/3007.003.0017"},{"key":"1_CR50","doi-asserted-by":"crossref","unstructured":"Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. J. ACM 40(1) (1993)","DOI":"10.1145\/138027.138042"},{"key":"1_CR51","unstructured":"Quattoni, A., Balle, B., Carreras, X., Globerson, A.: Spectral regularization for max-margin sequence tagging. In: Proceedings of ICML (2014)"},{"key":"1_CR52","doi-asserted-by":"crossref","unstructured":"Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Springer (1978)","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"1_CR53","doi-asserted-by":"crossref","unstructured":"Sch\u00fctzenberger, M.P.: On a special class of recurrent events. The Annals of Mathematical Statistics 32(4) (1961)","DOI":"10.1214\/aoms\/1177704860"},{"key":"1_CR54","doi-asserted-by":"crossref","unstructured":"Sch\u00fctzenberger, M.P.: On the definition of a family of automata. Information and Control 4 (1961)","DOI":"10.1016\/S0019-9958(61)80020-X"},{"key":"1_CR55","unstructured":"Sproat, R.: A finite-state architecture for tokenization and grapheme-to-phoneme conversion in multilingual text analysis. In: Proceedings of the ACL SIGDAT Workshop. ACL (1995)"},{"key":"1_CR56","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11) (1984)","DOI":"10.1145\/1968.1972"},{"key":"1_CR57","doi-asserted-by":"crossref","unstructured":"Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., Carrasco, R.C.: Probabilistic finite-state machines - part I. PAMI (2005)","DOI":"10.1109\/TPAMI.2005.147"}],"container-title":["Lecture Notes in Computer Science","Algebraic Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23021-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:46:21Z","timestamp":1718066781000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23021-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319230207","9783319230214"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23021-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"9 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}