Abstract
In this paper, we study active learning algorithms for weighted automata over a semiring. We show that a variant of Angluin’s seminal \(\mathtt {L}^{\!\star }\) algorithm works when the semiring is a principal ideal domain, but not for general semirings such as the natural numbers.
The research leading to this research was partially funded by the European Union’s Horizon 2020 research and innovation programme under the ERC Starting Grant ProFoundNet (grant code 679127) and the Marie Skłodowska-Curie Grant Agreement No. 795119, and the EPSRC Standard Grant CLeVer (EP/S028641/1).
Chapter PDF
Similar content being viewed by others
References
Fides Aarts, Paul Fiterau-Brostean, Harco Kuppens, and Frits W. Vaandrager. Learning register automata with fresh value generation. In Martin Leucker, Camilo Rueda, and Frank D. Valencia, editors, ICTAC, volume 9399 of LNCS, pages 165–183. Springer, 2015.
Cyril Allauzen, Mehryar Mohri, and Ameet Talwalkar. Sequence kernels for predicting protein essentiality. In William W. Cohen, Andrew McCallum, and Sam T. Roweis, editors, ICML, volume 307 of ACM International Conference Proceeding Series, pages 9–16. ACM, 2008.
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–227. Springer, 2011.
Dana Angluin. Learning regular sets from queries and counterexamples. Information and computation, 75(2):87–106, 1987.
Borja Balle and Mehryar Mohri. Spectral learning of general weighted automata via constrained matrix completion. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C.Burges, Léon Bottou, and Kilian Q. Weinberger, editors, NIPS, pages 2168–2176, 2012.
Borja Balle and Mehryar Mohri. Learning weighted automata. In Andreas Maletti, editor, CAI, volume 9270 of LNCS, pages 1–21. Springer, 2015.
Francesco Bergadano and Stefano Varricchio. Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput., 25(6):1268–1280, December 1996.
Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA. In Craig Boutilier, editor, IJCAI, pages 1004–1009, 2009.
Michele Boreale. Weighted bisimulation in linear algebraic form. In CONCUR, volume 5710 of LNCS, pages 163–177. Springer, 2009.
Jack W. Carlyle and Azaria Paz. Realizations by stochastic finite automata. J. Comput. Syst. Sci., 5(1):26–40, 1971.
Karel Culik II and Jarkko Kari. Image compression using weighted finite automata. Computers & Graphics, 17(3):305–313, 1993.
Michel Fliess. Matrices de Hankel. J. Math. Pures Appl, 53(9):197–222, 1974.
Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva. Optimizing automata learning via monads. arXiv preprint arXiv:1704.08055, 2017.
Falk Howar and Bernhard Steffen. Active automata learning in practice - an annotated bibliography of the years 2011 to 2016. In Amel Bennaceur, Reiner Hähnle, and Karl Meinke, editors, Machine Learning for Dynamic Software Analysis: Potentials and Limits -International Dagstuhl Seminar 16172, volume 11026 of LNCS, pages 123–148. Springer, 2018.
Malte Isberner, Falk Howar, and Bernhard Steffen. The open-source learnlib - A framework for active automata learning. In Daniel Kroening and Corina S. Pasareanu, editors, CAV,volume 9206 of LNCS, pages 487–495. Springer, 2015.
Nathan Jacobson. Lectures in Abstract Algebra, volume 31 of GTM. Springer, 1953.
Nathan Jacobson. Basic algebra I. Courier Corporation, 2012.
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–425, 1994.
Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. Inform. and Comput., 118:316–326, 1995.
Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michal Szynwelski. Learning nominal automata. In Giuseppe Castagna and Andrew D. Gordon, editors, POPL, pages 613–625. ACM, 2017.
Mehryar Mohri, Fernando Pereira, and Michael Riley. Weighted automata in text and speech processing.CoRR, abs/cs/0503077, 2005.
Malte Mues, Falk Howar, Kasper Søe 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–5, 2016.
Morris Orzech. Onto endomorphisms are isomorphisms. The American Mathematical Monthly, 78(4):357–362, 1971.
Muzammil Shahbaz and Roland Groz. Inferring Mealy machines. In FM, volume 5850 of LNCS, pages 207–222, Berlin, Heidelberg, 2009. Springer-Verlag.
Henry J. Stephen Smith. On systems of linear indeterminate equations and congruences. Philosophical Transactions of the Royal Society of London, 151:293–326, 1861.
Martin Tappler, Bernhard K. Aichernig, Giovanni Bacci, Maria Eichlseder, and Kim G. Larsen. L\({}^{\text{*}}\)-Based Learning of Markov Decision Processes. In Maurice H. ter Beek, Annabelle McIver, and José N. Oliveira, editors, FM, volume 11800 of LNCS, pages 651–669. Springer, 2019.
Frits W. Vaandrager. Model learning. Commun. ACM, 60(2):86–95, 2017.
Juan Miguel Vilar. Query learning of subsequential transducers. In ICGI, volume 1147 of LNCS, pages 72–83. Springer, 1996.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
van Heerdt, G., Kupke, C., Rot, J., Silva, A. (2020). Learning Weighted Automata over Principal Ideal Domains. In: Goubault-Larrecq, J., König, B. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2020. Lecture Notes in Computer Science(), vol 12077. Springer, Cham. https://doi.org/10.1007/978-3-030-45231-5_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-45231-5_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45230-8
Online ISBN: 978-3-030-45231-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)