{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T08:12:57Z","timestamp":1778832777185,"version":"3.51.4"},"reference-count":73,"publisher":"Cambridge University Press (CUP)","issue":"8","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"unspecified","delay-in-days":68,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study the approximate minimization problem of weighted finite automata (WFAs): to compute the best possible approximation of a WFA given a bound on the number of states. By reformulating the problem in terms of Hankel matrices, we leverage classical results on the approximation of Hankel operators, namely the celebrated Adamyan-Arov-Krein (AAK) theory. We solve the optimal spectral-norm approximate minimization problem for irredundant WFAs with real weights, defined over a one-letter alphabet. We present a theoretical analysis based on AAK theory and bounds on the quality of the approximation in the spectral norm and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000276_inline1.png\"\/><jats:tex-math>\n$\\ell ^2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> norm. Moreover, we provide a closed-form solution, and an algorithm, to compute the optimal approximation of a given size in polynomial time.<\/jats:p>","DOI":"10.1017\/s0960129524000276","type":"journal-article","created":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T07:50:33Z","timestamp":1731052233000},"page":"807-833","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Optimal approximate minimization of one-letter weighted finite automata"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2087-7630","authenticated-orcid":false,"given":"Clara","family":"Lacroce","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Borja","family":"Balle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8763-6172","authenticated-orcid":false,"given":"Prakash","family":"Panangaden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8090-2810","authenticated-orcid":false,"given":"Guillaume","family":"Rabusseau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"S0960129524000276_ref60","unstructured":"Popescu, G. (1993). Noncommutative dilation theory on Fock spaces. PhD thesis. Texas A&M University."},{"key":"S0960129524000276_ref55","volume-title":"Hankel Operators and Their Applications","author":"Peller","year":"2012"},{"key":"S0960129524000276_ref14","doi-asserted-by":"crossref","unstructured":"Balle, B. , Panangaden, P. and Precup, D. (2015). A Canonical Form for Weighted Automata and Applications to Approximate Minimization. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), Kyoto, Japan: IEEE Computer Society. 701\u2013712.","DOI":"10.1109\/LICS.2015.70"},{"key":"S0960129524000276_ref68","first-page":"221","article-title":"Approximating probabilistic models as weighted finite automata","volume":"47","author":"Theertha Suresh","year":"(2021)","journal-title":"Comput. Linguistics"},{"key":"S0960129524000276_ref59","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(92)90214-X"},{"key":"S0960129524000276_ref22","doi-asserted-by":"crossref","unstructured":"Bonchi, F. , Bonsangue, M. , Rutten, J. and Silva, A. (2012b) Brzozowski\u2019s algorithm (co)algebraically, Constable, R. and Silva, A. , (eds.) Logics and Program Semantics: Essays Dedicated to Dexter Kozen, Lecture Notes In Computer Science, vol. 7230, Springer-Verlag, 12\u201323.","DOI":"10.1007\/978-3-642-29485-3_2"},{"key":"S0960129524000276_ref39","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1997.9.8.1735"},{"key":"S0960129524000276_ref21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2631916","article-title":"Algebra-coalgebra duality in Brzozowski\u2019s minimization algorithm","volume":"15","author":"Bonchi","year":"2014","journal-title":"ACM Transactions On Computational Logic"},{"key":"S0960129524000276_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(84)90098-3"},{"key":"S0960129524000276_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.025"},{"key":"S0960129524000276_ref54","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(62)90030-6"},{"key":"S0960129524000276_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104649"},{"key":"S0960129524000276_ref53","doi-asserted-by":"crossref","unstructured":"Okudono, T. , Waga, M. , Sekiyama, T. and Hasuo, I. (2020). Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI. 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI. 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI. 2020, New York, NY, USA, February 7-12, 2020, AAAI Press. 5306\u20135314.","DOI":"10.1609\/aaai.v34i04.5977"},{"key":"S0960129524000276_ref57","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1989-0972704-3"},{"key":"S0960129524000276_ref69","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574"},{"key":"S0960129524000276_ref46","unstructured":"Kulesza, A. , Rao, N. R. and Singh, S. (2014). Low-Rank Spectral Learning. In: Kaski, S. and Corander, J. (eds.) Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research (PMLR), Reykjavik, Iceland, 33, 522\u2013530."},{"key":"S0960129524000276_ref19","first-page":"191","volume-title":"Logic, Language, Information and Computation - 19th International Workshop, WoLLIC. 2012, Buenos Aires Proceedings, of Lecture Notes in Computer Science, vol. 7456","author":"Bezhanishvili","year":"2012"},{"key":"S0960129524000276_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.12.002"},{"key":"S0960129524000276_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"S0960129524000276_ref23","unstructured":"Brzozowski, J. A. (1962). Canonical regular expressions and minimal state graphs for definite events. In: Fox, J. , (ed.) Proceedings of the Symposium on Mathematical Theory of Automata, in MRI Symposia Series, Polytechnic Press of the Polytechnic Institute of Brooklyn, 12 529\u2013561."},{"key":"S0960129524000276_ref34","first-page":"197","article-title":"Matrice de Hankel","volume":"5","author":"Fliess","year":"1974","journal-title":"Journal De Math\u00e9matique Pures et Appliqu\u00e9es"},{"key":"S0960129524000276_ref41","first-page":"95","volume-title":"Linear Algebra and Its Application","author":"Ionescu","year":"2001"},{"key":"S0960129524000276_ref47","unstructured":"Lacroce, C. (2022). The Approximate Minimization Problem of Weighted Finite Automata and Applications to Language Modelling: An Approach Based on Adamyan-Arov-Krein Theory. PhD thesis. McGill University."},{"key":"S0960129524000276_ref1","doi-asserted-by":"publisher","DOI":"10.1070\/SM1971v015n01ABEH001531"},{"key":"S0960129524000276_ref36","doi-asserted-by":"publisher","DOI":"10.1080\/00207178408933239"},{"key":"S0960129524000276_ref10","unstructured":"Balle, B. , Gourdeau, P. and Panangaden, P. (2017) Bisimulation metrics and norms for weighted finite automata, In: Chatzigiannakis, I. , Indyk, P. , Kuhn, F. and Muscholl, A. (eds.) 44th International Colloquium On Automata, Languages, and Programming, ICALP, volume 80 of LIPIcs, Warsaw, Poland, 103:1\u2013103:14, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. 2017,"},{"key":"S0960129524000276_ref37","doi-asserted-by":"publisher","DOI":"10.1080\/00207170500110988"},{"key":"S0960129524000276_ref29","first-page":"1035","article-title":"Rational kernels: theory and Algorithms","volume":"5","author":"Cortes","year":"2004","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"S0960129524000276_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(71)80005-3"},{"key":"S0960129524000276_ref65","doi-asserted-by":"publisher","DOI":"10.1007\/s00020-012-2012-6"},{"key":"S0960129524000276_ref67","first-page":"392","article-title":"The equations ax - yb = c and ax - xb = c in matrices","volume":"3","author":"Roth","year":"1952","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S0960129524000276_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104654"},{"key":"S0960129524000276_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5"},{"key":"S0960129524000276_ref2","doi-asserted-by":"crossref","unstructured":"Al-Hussari, M. , Jaimoukha, I. and Limebeer, D. (1993). A descriptor approach for the solution of the one-block distance problem. In: Proceedings of the IFAC World Congress.","DOI":"10.1016\/S1474-6670(17)49232-9"},{"key":"S0960129524000276_ref28","volume-title":"Discrete H\u221e Optimization With Applications in Signal Processing and Control Systems","author":"Chui","year":"1997"},{"key":"S0960129524000276_ref13","unstructured":"Balle, B. , Lacroce, C. , Panangaden, P. , Precup, D. and Rabusseau, G. (2021) Optimal spectral-norm approximate minimization of weighted finite automata, In: Bansal, N. , Merelli, E. and Worrell, J. (eds.) 48th International Colloquium On Automata, Languages, and Programming, ICALP, vol.198, Glasgow, Scotland (Virtual Conference), 118, LIPIcs"},{"key":"S0960129524000276_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553379"},{"key":"S0960129524000276_ref63","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2006.07.004"},{"key":"S0960129524000276_ref18","volume-title":"Noncommutative Rational Series with Applications","author":"Berstel","year":"2011"},{"key":"S0960129524000276_ref73","volume-title":"Operator Theory in Function Spaces","author":"Zhu","year":"1990"},{"key":"S0960129524000276_ref64","doi-asserted-by":"publisher","DOI":"10.1090\/S0065-9266-09-00587-0"},{"key":"S0960129524000276_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/361573.361582"},{"key":"S0960129524000276_ref38","article-title":"Distilling the knowledg","author":"Hinton","year":"2015","journal-title":"CoRR"},{"key":"S0960129524000276_ref61","doi-asserted-by":"publisher","DOI":"10.1007\/BF01460977"},{"key":"S0960129524000276_ref52","volume-title":"volume 92 of Mathematical Surveys and Monographs","author":"Nikol\u2019Skii","year":"2002"},{"key":"S0960129524000276_ref71","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(73)90190-X"},{"key":"S0960129524000276_ref44","first-page":"535","article-title":"Zur Theorie der elimination einer Variablen aus zwei algebraischen Gleichungen","author":"Kronecker","year":"1881","journal-title":"Montasber. K\u00f6nigl. Preussischen Acad Wies"},{"key":"S0960129524000276_ref72","doi-asserted-by":"crossref","unstructured":"Zhang, X. , Du, X. , Xie, X. , Ma, L. , Liu, Y. and Sun, M. (2021). Decision-guided weighted automata extraction from recurrent neural networks. In: Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI. 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI. 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI. 2021, Virtual Event, AAAI Press. 11699\u201311707, Virtual Event, February 2-9, 2021.","DOI":"10.1609\/aaai.v35i13.17391"},{"key":"S0960129524000276_ref66","unstructured":"Rabusseau, G. , Li, T. and Precup, D. (2019). Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning. In: Chaudhuri, K. and Sugiyama, M. (eds.) The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS. 2019, volume 89 of Proceedings of Machine Learning Research (PMLR), Naha, Okinawa, Japan, 1630\u20131639."},{"key":"S0960129524000276_ref70","unstructured":"Weiss, G. , Goldberg, Y. and Yahav, E. (2019). Learning Deterministic Weighted Automata with Queries and Counterexamples. In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 (NeurIPS), December 8-14, 2019, Vancouver, BC, Canada, 8558\u20138569."},{"key":"S0960129524000276_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/0325022"},{"key":"S0960129524000276_ref49","article-title":"Towards an AAK theory approach to approximate minimization in the multi-letter case","author":"Lacroce","year":"2022","journal-title":"CoRR"},{"key":"S0960129524000276_ref42","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8418"},{"key":"S0960129524000276_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5416-x"},{"key":"S0960129524000276_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-99154-2_7"},{"key":"S0960129524000276_ref12","unstructured":"Balle, B. , Hamilton, W. L. and Pineau, J. (2014 b). Methods of Moments for Learning Stochastic Languages: Unified Presentation and Empirical Comparison, In: Proceedings of the 31th International Conference on Machine Learning (ICML), volume 32 of JMLR Workshop and Conference Proceedings, Beijing, China, 1386\u20131394."},{"key":"S0960129524000276_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01198485"},{"key":"S0960129524000276_ref50","unstructured":"Lyapunov, A. M. (1950). The general problem of the stability of motion [in Russian]. Gostekhizdat, Moscow, Elsevier."},{"key":"S0960129524000276_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(82)90057-X"},{"key":"S0960129524000276_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288367"},{"key":"S0960129524000276_ref45","first-page":"517","volume-title":"Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research","author":"Kulesza","year":"2015"},{"key":"S0960129524000276_ref62","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-1236(03)00078-8"},{"key":"S0960129524000276_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-021-05948-1"},{"key":"S0960129524000276_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/9781009004305"},{"key":"S0960129524000276_ref48","unstructured":"Lacroce, C. , Panangaden, P. and Rabusseau, G. (2021). Extracting weighted automata for approximate minimization in language modelling. In: Chandlee, J. , Eyraud, R. , Heinz, J. , Jardine, A. and van Zaanen, M. (eds.) Proceedings of the Fifteenth International Conference on Grammatical Inference, volume 153 of Proceedings of Machine Learning Research (PMLR), 153, 92\u2013112."},{"key":"S0960129524000276_ref30","first-page":"41","article-title":"On rational stochastic languages","volume":"86","author":"Denis","year":"2008","journal-title":"Fundamenta Informaticae"},{"key":"S0960129524000276_ref43","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7402948"},{"key":"S0960129524000276_ref51","doi-asserted-by":"publisher","DOI":"10.2307\/1969670"},{"key":"S0960129524000276_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129519000094"},{"key":"S0960129524000276_ref56","doi-asserted-by":"publisher","DOI":"10.1142\/S012905411540002X"},{"key":"S0960129524000276_ref5","unstructured":"Ayache, S. , Eyraud, R. and Goudian, N. (2018). Explaining Black Boxes on Sequential Data Using Weighted Automata, In: Proceedings of the 14th International Conference on Grammatical Inference, ICGI. 2018, volume 93 of Proceedings of Machine Learning Research (PMLR) Wroc\u0142aw, Poland, September 5-7, 201881\u2013103."},{"key":"S0960129524000276_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718713"},{"key":"S0960129524000276_ref58","first-page":"355","article-title":"Models for infinite sequences of noncommuting operators","volume":"53","author":"Popescu","year":"1989","journal-title":"Acta Scientiarum Mathematicarum"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129524000276","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T09:02:49Z","timestamp":1738832569000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129524000276\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":73,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["S0960129524000276"],"URL":"https:\/\/doi.org\/10.1017\/s0960129524000276","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}