{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T20:12:27Z","timestamp":1784837547213,"version":"3.55.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030452308","type":"print"},{"value":"9783030452315","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin\u2019s seminal <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathtt {L}^{\\!\\star }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mo>\u22c6<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers.<\/jats:p>","DOI":"10.1007\/978-3-030-45231-5_31","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"602-621","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Learning Weighted Automata over Principal Ideal Domains"],"prefix":"10.1007","author":[{"given":"Gerco","family":"van Heerdt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Clemens","family":"Kupke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jurriaan","family":"Rot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandra","family":"Silva","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Fides Aarts, Paul Fiterau-Brostean, Harco Kuppens, and Frits\u00a0W. Vaandrager. Learning register automata with fresh value generation. In Martin Leucker, Camilo Rueda, and Frank\u00a0D. Valencia, editors, ICTAC, volume 9399 of LNCS, pages 165\u2013183. Springer, 2015.","DOI":"10.1007\/978-3-319-25150-9_11"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Cyril Allauzen, Mehryar Mohri, and Ameet Talwalkar. Sequence kernels for predicting protein essentiality. In William\u00a0W. Cohen, Andrew McCallum, and Sam\u00a0T. Roweis, editors, ICML, volume 307 of ACM International Conference Proceeding Series, pages 9\u201316. ACM, 2008.","DOI":"10.1145\/1390156.1390158"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Benjamin Aminof, Orna Kupferman, and Robby Lampert. Formal analysis of online algorithms. In Tevfik Bultan and Pao-Ann Hsiung, editors, ATVA, volume 6996 of LNCS, pages 213\u2013227. Springer, 2011.","DOI":"10.1007\/978-3-642-24372-1_16"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Dana Angluin. Learning regular sets from queries and counterexamples. Information and computation, 75(2):87\u2013106, 1987.","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"31_CR5","unstructured":"Borja Balle and Mehryar Mohri. Spectral learning of general weighted automata via constrained matrix completion. In Peter\u00a0L. Bartlett, Fernando C.\u00a0N. Pereira, Christopher J.\u00a0C.Burges, L\u00e9on Bottou, and Kilian\u00a0Q. Weinberger, editors, NIPS, pages 2168\u20132176, 2012."},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Borja Balle and Mehryar Mohri. Learning weighted automata. In Andreas Maletti, editor, CAI, volume 9270 of LNCS, pages 1\u201321. Springer, 2015.","DOI":"10.1007\/978-3-319-23021-4_1"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Francesco Bergadano and Stefano Varricchio. Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput., 25(6):1268\u20131280, December 1996.","DOI":"10.1137\/S009753979326091X"},{"key":"31_CR8","unstructured":"Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA. In Craig Boutilier, editor, IJCAI, pages 1004\u20131009, 2009."},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Michele Boreale. Weighted bisimulation in linear algebraic form. In CONCUR, volume 5710 of LNCS, pages 163\u2013177. Springer, 2009.","DOI":"10.1007\/978-3-642-04081-8_12"},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"Jack\u00a0W. Carlyle and Azaria Paz. Realizations by stochastic finite automata. J. Comput. Syst. Sci., 5(1):26\u201340, 1971.","DOI":"10.1016\/S0022-0000(71)80005-3"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Karel Culik\u00a0II and Jarkko Kari. Image compression using weighted finite automata. Computers & Graphics, 17(3):305\u2013313, 1993.","DOI":"10.1016\/0097-8493(93)90079-O"},{"key":"31_CR12","unstructured":"Michel Fliess. Matrices de Hankel. J. Math. Pures Appl, 53(9):197\u2013222, 1974."},{"key":"31_CR13","unstructured":"Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva. Optimizing automata learning via monads. arXiv preprint arXiv:1704.08055, 2017."},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Falk Howar and Bernhard Steffen. Active automata learning in practice - an annotated bibliography of the years 2011 to 2016. In Amel Bennaceur, Reiner H\u00e4hnle, and Karl Meinke, editors, Machine Learning for Dynamic Software Analysis: Potentials and Limits -International Dagstuhl Seminar 16172, volume 11026 of LNCS, pages 123\u2013148. Springer, 2018.","DOI":"10.1007\/978-3-319-96562-8_5"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Malte Isberner, Falk Howar, and Bernhard Steffen. The open-source learnlib - A framework for active automata learning. In Daniel Kroening and Corina\u00a0S. Pasareanu, editors, CAV,volume 9206 of LNCS, pages 487\u2013495. Springer, 2015.","DOI":"10.1007\/978-3-319-21690-4_32"},{"key":"31_CR16","doi-asserted-by":"crossref","unstructured":"Nathan Jacobson. Lectures in Abstract Algebra, volume\u00a031 of GTM. Springer, 1953.","DOI":"10.1007\/978-1-4684-7053-6_2"},{"key":"31_CR17","unstructured":"Nathan Jacobson. Basic algebra I. Courier Corporation, 2012."},{"key":"31_CR18","doi-asserted-by":"crossref","unstructured":"Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. International Journal of Algebra and Computation, 4(3):405\u2013425, 1994.","DOI":"10.1142\/S0218196794000063"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. Inform. and Comput., 118:316\u2013326, 1995.","DOI":"10.1006\/inco.1995.1070"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michal Szynwelski. Learning nominal automata. In Giuseppe Castagna and Andrew\u00a0D. Gordon, editors, POPL, pages 613\u2013625. ACM, 2017.","DOI":"10.1145\/3093333.3009879"},{"key":"31_CR21","unstructured":"Mehryar Mohri, Fernando Pereira, and Michael Riley. Weighted automata in text and speech processing.CoRR, abs\/cs\/0503077, 2005."},{"key":"31_CR22","unstructured":"Malte Mues, Falk Howar, Kasper\u00a0S\u00f8e Luckow, Temesghen Kahsai, and Zvonimir Rakamaric. Releasing the PSYCO: using symbolic search in interface generation for java.ACM SIGSOFT Software Engineering Notes, 41(6):1\u20135, 2016."},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"Morris Orzech. Onto endomorphisms are isomorphisms. The American Mathematical Monthly, 78(4):357\u2013362, 1971.","DOI":"10.1080\/00029890.1971.11992759"},{"key":"31_CR24","doi-asserted-by":"crossref","unstructured":"Muzammil Shahbaz and Roland Groz. Inferring Mealy machines. In FM, volume 5850 of LNCS, pages 207\u2013222, Berlin, Heidelberg, 2009. Springer-Verlag.","DOI":"10.1007\/978-3-642-05089-3_14"},{"key":"31_CR25","doi-asserted-by":"crossref","unstructured":"Henry J.\u00a0Stephen Smith. On systems of linear indeterminate equations and congruences. Philosophical Transactions of the Royal Society of London, 151:293\u2013326, 1861.","DOI":"10.1098\/rstl.1861.0016"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"Martin Tappler, Bernhard\u00a0K. Aichernig, Giovanni Bacci, Maria Eichlseder, and Kim\u00a0G. Larsen. L$${}^{\\text{*}}$$-Based Learning of Markov Decision Processes. In Maurice\u00a0H. ter Beek, Annabelle McIver, and Jos\u00e9\u00a0N. Oliveira, editors, FM, volume 11800 of LNCS, pages 651\u2013669. Springer, 2019.","DOI":"10.1007\/978-3-030-30942-8_38"},{"key":"31_CR27","doi-asserted-by":"crossref","unstructured":"Frits\u00a0W. Vaandrager. Model learning. Commun. ACM, 60(2):86\u201395, 2017.","DOI":"10.1145\/2967606"},{"key":"31_CR28","doi-asserted-by":"crossref","unstructured":"Juan\u00a0Miguel Vilar. Query learning of subsequential transducers. In ICGI, volume 1147 of LNCS, pages 72\u201383. Springer, 1996.","DOI":"10.1007\/BFb0033343"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45231-5_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T14:05:28Z","timestamp":1610028328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45231-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030452308","9783030452315"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45231-5_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dublin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2020","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":"fossacs2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"98","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference could not take place due to the COVID-19 pandemic. There was an online event on July 2, 2020.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}