{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T09:46:26Z","timestamp":1785750386231,"version":"3.56.0"},"reference-count":79,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T00:00:00Z","timestamp":1785715200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T00:00:00Z","timestamp":1785715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007051","name":"Uppsala University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007051","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Autom Reasoning"],"published-print":{"date-parts":[[2026,12]]},"abstract":"Abstract<\/jats:title>\n \n Existing active automata learning (AAL) algorithms have demonstrated their potential in capturing the behavior of complex systems (e.g., in analyzing network protocol implementations). The most widely used AAL algorithms generate finite state machine models, such as Mealy machines or deterministic finite automata. For many analysis tasks, however, it is crucial to generate richer classes of models that also show how relations between data parameters affect system behavior. Such models have shown potential to uncover critical bugs, but their learning algorithms do not scale beyond small and well curated experiments. In this article, we present\n \n \n $${SL}^{\\lambda }$$<\/jats:tex-math>\n \n \n \n SL<\/mml:mi>\n <\/mml:mrow>\n \u03bb<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , an effective and scalable register automata (RA) learning algorithm that significantly reduces the number of membership queries required for inferring models. It achieves this by combining a tree-based cost-efficient data structure with mechanisms for computing short and restricted tests. We prove that\n \n \n $${SL}^{\\lambda }$$<\/jats:tex-math>\n \n \n \n SL<\/mml:mi>\n <\/mml:mrow>\n \u03bb<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is guaranteed to learn an acceptor, in the form of a register automaton with\n n<\/jats:italic>\n locations and\n t<\/jats:italic>\n transitions, for a given data language of finite index, and that it can do so with at most\n \n \n $$O(t^2 \\, (2n)^n + m t^2 \\, m^m)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n t<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \n \n (<\/mml:mo>\n 2<\/mml:mn>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n +<\/mml:mo>\n m<\/mml:mi>\n \n t<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \n m<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n membership queries and\n O<\/jats:italic>\n (\n t<\/jats:italic>\n ) equivalence queries, where\n m<\/jats:italic>\n is the length of the longest counterexample received during learning. We have implemented\n \n \n $${SL}^{\\lambda }$$<\/jats:tex-math>\n \n \n \n SL<\/mml:mi>\n <\/mml:mrow>\n \u03bb<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n as a new algorithm in RALib. We evaluate its performance by comparing it against\n \n \n $${SL}^{*}$$<\/jats:tex-math>\n \n \n \n SL<\/mml:mi>\n <\/mml:mrow>\n \n \n \n \u2217<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mmultiscripts>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , the current state-of-the-art RA learning algorithm. Experiments on a series of benchmarks show that it reduces the number of membership queries by up to an order of magnitude, and also shows substantial asymptotic improvements in bigger systems.\n <\/jats:p>","DOI":"10.1007\/s10817-026-09758-9","type":"journal-article","created":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T09:04:00Z","timestamp":1785747840000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["$${SL}^{\\lambda }$$: A Scalable Algorithm for Register Automata Learning"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9730-9335","authenticated-orcid":false,"given":"Simon","family":"Dierl","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5185-0035","authenticated-orcid":false,"given":"Paul","family":"Fiter\u0103u-Bro\u015ftean","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9524-4459","authenticated-orcid":false,"given":"Falk","family":"Howar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7897-601X","authenticated-orcid":false,"given":"Bengt","family":"Jonsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9657-0179","authenticated-orcid":false,"given":"Konstantinos","family":"Sagonas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4066-9078","authenticated-orcid":false,"given":"Fredrik","family":"T\u00e5quist","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,3]]},"reference":[{"key":"9758_CR1","doi-asserted-by":"publisher","unstructured":"Aarts, F., Jonsson, B., Uijen, J., Vaandrager, F.: Generating models of infinite-state communication protocols using regular inference with abstraction. Formal Methods in System Design, 1\u201341 (2015) https:\/\/doi.org\/10.1007\/s10703-014-0216-x","DOI":"10.1007\/s10703-014-0216-x"},{"key":"9758_CR2","unstructured":"Aarts, F., Kuppens, H., Tretmans, J., Vaandrager, F.W., Verwer, S.: Learning and testing the bounded retransmission protocol. In: Proceedings of the Eleventh International Conference on Grammatical Inference, ICGI 2012. JMLR Proceedings, vol. 21, pp. 4\u201318. JMLR.org, College Park, MA, USA (2012). http:\/\/proceedings.mlr.press\/v21\/aarts12a.html"},{"key":"9758_CR3","doi-asserted-by":"publisher","unstructured":"Aarts, F., Heidarian, F., Kuppens, H., Olsen, P., Vaandrager, F.: Automata learning through counterexample guided abstraction refinement. In: Giannakopoulou, D., M\u00e9ry, D. (eds.) FM 2012: Formal Methods. LNCS, vol. 7436, pp. 10\u201327. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32759-9_4","DOI":"10.1007\/978-3-642-32759-9_4"},{"key":"9758_CR4","doi-asserted-by":"publisher","unstructured":"Aarts, F., Fiter\u0103u-Bro\u015ftean, P., Kuppens, H., Vaandrager, F.: Learning register automata with fresh value generation. In: Leucker, M., Rueda, C., Valencia, F.D. (eds.) Theoretical Aspects of Computing - ICTAC 2015. LNCS, vol. 9399, pp. 165\u2013183. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-25150-9_11","DOI":"10.1007\/978-3-319-25150-9_11"},{"issue":"1","key":"9758_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10703-014-0216-x","volume":"46","author":"F Aarts","year":"2015","unstructured":"Aarts, F., Jonsson, B., Uijen, J., Vaandrager, F.: Generating models of infinite-state communication protocols using regular inference with abstraction. Formal Methods in System Design 46(1), 1\u201341 (2015). https:\/\/doi.org\/10.1007\/s10703-014-0216-x","journal-title":"Formal Methods in System Design"},{"key":"9758_CR6","doi-asserted-by":"publisher","unstructured":"Alur, R., D\u2019Antoni, L., Deshmukh, J.V., Raghothaman, M., Yuan, Y.: Regular functions and cost register automata. In: Proceedings of the 2013 28th Annual ACM\/IEEE Symposium on Logic in Computer Science. LICS \u201913, pp. 13\u201322. IEEE Computer Society, Los Alamitos, CA (2013). https:\/\/doi.org\/10.1109\/LICS.2013.65","DOI":"10.1109\/LICS.2013.65"},{"key":"9758_CR7","doi-asserted-by":"publisher","unstructured":"Ammons, G., Bod\u00edk, R., Larus, J.R.: Mining specifications. In: Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL \u201902, pp. 4\u201316. ACM, New York, NY, USA (2002). https:\/\/doi.org\/10.1145\/503272.503275","DOI":"10.1145\/503272.503275"},{"issue":"2","key":"9758_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987). https:\/\/doi.org\/10.1016\/0890-5401(87)90052-6","journal-title":"Inf. Comput."},{"key":"9758_CR9","doi-asserted-by":"publisher","unstructured":"Balachander, M., Filiot, E., Gentilini, R., Tzevelekos, N.: Register automata with permutations. In: 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol. 345, pp. 14\u201311418. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2025). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2025.14","DOI":"10.4230\/LIPIcs.MFCS.2025.14"},{"key":"9758_CR10","doi-asserted-by":"publisher","unstructured":"Balachander, M., Filiot, E., Gentilini, R.: Passive learning of regular data languages in polynomial time and data. In: 35th International Conference on Concurrency Theory (CONCUR). Leibniz International Proceedings in Informatics (LIPIcs), vol. 311, pp. 10\u201311021. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2024.10","DOI":"10.4230\/LIPIcs.CONCUR.2024.10"},{"key":"9758_CR11","unstructured":"Benedikt, M., Ley, C., Puppis, G.: What you must remember when processing data words. In: Proceedings 4th Alberto Mendelzon International Workshop on Foundations of Data Management. CEUR Workshop Proceedings, vol. 619 (2010). http:\/\/ceur-ws.org\/Vol-619\/paper11.pdf"},{"key":"9758_CR12","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-10(3:4)2014","author":"M Boja\u0144czyk","year":"2014","unstructured":"Boja\u0144czyk, M., Klin, B., Lasota, S.: Automata theory in nominal sets. Logical Methods in Computer Science (2014). https:\/\/doi.org\/10.2168\/LMCS-10(3:4)2014","journal-title":"Logical Methods in Computer Science"},{"key":"9758_CR13","doi-asserted-by":"publisher","unstructured":"Bollig, B., Habermehl, P., Leucker, M., Monmege, B.: A fresh approach to learning register automata. In: Developments in Language Theory. LNCS, vol. 7907, pp. 118\u2013130. Springer, Berlin, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38771-5_12","DOI":"10.1007\/978-3-642-38771-5_12"},{"key":"9758_CR14","doi-asserted-by":"publisher","unstructured":"Bruy\u00e8re, V., Garhewal, B., P\u00e9rez, G.A., Staquet, G., Vaandrager, F.W.: Active learning of Mealy machines with timers. In: Prabhakar, P., Vandin, A. (eds.) International Conference on Quantitative Evaluation of Systems and Formal Modeling and Analysis of Timed Systems. LNCS, vol. 16143, pp. 42\u201361. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-032-05792-1_3","DOI":"10.1007\/978-3-032-05792-1_3"},{"issue":"1","key":"9758_CR15","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.jlamp.2014.07.004","volume":"84","author":"S Cassel","year":"2015","unstructured":"Cassel, S., Howar, F., Jonsson, B., Merten, M., Steffen, B.: A succinct canonical register automaton model. J. Log. Algebr. Meth. Program. 84(1), 54\u201366 (2015). https:\/\/doi.org\/10.1016\/j.jlamp.2014.07.004","journal-title":"J. Log. Algebr. Meth. Program."},{"key":"9758_CR16","unstructured":"Cassel, S., Howar, F., Jonsson, B.: RALib: a LearnLib extension for inferring EFSMs. In: Proceedings of the 4th International Workshop on Design and Implementation of Formal Tools and Systems (DIFTS), pp. 1\u20138 (2015). https:\/\/www.faculty.ece.vt.edu\/chaowang\/difts2015\/papers\/paper_5.pdf"},{"issue":"2","key":"9758_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00165-016-0355-5","volume":"28","author":"S Cassel","year":"2016","unstructured":"Cassel, S., Howar, F., Jonsson, B., Steffen, B.: Active learning for extended finite state machines. Formal Asp. Comput. 28(2), 233\u2013263 (2016). https:\/\/doi.org\/10.1007\/s00165-016-0355-5","journal-title":"Formal Asp. Comput."},{"key":"9758_CR18","doi-asserted-by":"publisher","unstructured":"Cassel, S., Howar, F., Jonsson, B., Steffen, B.: Extending automata learning to extended finite state machines. In: Bennaceur, A., H\u00e4hnle, R., Meinke, K. (eds.) Machine Learning for Dynamic Software Analysis: Potentials and Limits - International Dagstuhl Seminar 16172, Revised Papers. LNCS, vol. 11026, pp. 149\u2013177. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96562-8_6","DOI":"10.1007\/978-3-319-96562-8_6"},{"issue":"2","key":"9758_CR19","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.tcs.2004.03.072","volume":"330","author":"J-M Champarnaud","year":"2005","unstructured":"Champarnaud, J.-M., Parantho\u00ebn, T.: Random generation of DFAs. Theoret. Comput. Sci. 330(2), 221\u2013235 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2004.03.072","journal-title":"Theoret. Comput. Sci."},{"key":"9758_CR20","doi-asserted-by":"publisher","unstructured":"Chen, Y., Leng\u00e1l, O., Tan, T., Wu, Z.: Register automata with linear arithmetic. In: Proceedings of the 32nd ACM\/IEEE Symposium on Logic in Computer Science. LICS \u201917, pp. 1\u201312. IEEE Computer Society, Los Alamitos, CA (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005111","DOI":"10.1109\/LICS.2017.8005111"},{"key":"9758_CR21","doi-asserted-by":"publisher","unstructured":"Dierl, S., Howar, F.: A taxonomy and reductions for common register automata formalisms. In: Model Checking, Synthesis, and Learning. LNCS, vol. 13030, pp. 186\u2013218. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-91384-7_10","DOI":"10.1007\/978-3-030-91384-7_10"},{"key":"9758_CR22","doi-asserted-by":"publisher","unstructured":"Dierl, S., Fiter\u0103u-Bro\u015ftean, P., Howar, F., Jonsson, B., Sagonas, K., T\u00e5quist, F.: Scalable tree-based register automata learning. In: Tools and Algorithms for the Construction and Analysis of Systems - 30th International Conference, TACAS 2024, Proceedings, Part II. LNCS, vol. 14571, pp. 87\u2013108. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-57249-4_5","DOI":"10.1007\/978-3-031-57249-4_5"},{"key":"9758_CR23","doi-asserted-by":"publisher","unstructured":"Drews, S., D\u2019Antoni, L.: Learning symbolic automata. In: Legay, A., Margaria, T. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 10205, pp. 173\u2013189. Springer, Berlin, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54577-5_10","DOI":"10.1007\/978-3-662-54577-5_10"},{"key":"9758_CR24","unstructured":"Erinola, N., Maehren, M., Merget, R., Somorovsky, J., Schwenk, J.: Exploring the unknown $$\\{$$DTLS$$\\}$$ universe: Analysis of the $$\\{$$DTLS$$\\}$$ server ecosystem on the internet. In: 32nd USENIX Security Symposium (USENIX Security 23), pp. 4859\u20134876. USENIX Association, Anaheim, CA (2023). https:\/\/www.usenix.org\/conference\/usenixsecurity23\/presentation\/erinola"},{"issue":"1\u20133","key":"9758_CR25","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.scico.2007.01.015","volume":"69","author":"MD Ernst","year":"2007","unstructured":"Ernst, M.D., Perkins, J.H., Guo, P.J., McCamant, S., Pacheco, C., Tschantz, M.S., Xiao, C.: The Daikon system for dynamic detection of likely invariants. Sci. Comput. Program. 69(1\u20133), 35\u201345 (2007). https:\/\/doi.org\/10.1016\/j.scico.2007.01.015","journal-title":"Sci. Comput. Program."},{"issue":"3\u20134","key":"9758_CR26","doi-asserted-by":"publisher","first-page":"205","DOI":"10.3233\/FI-2011-607","volume":"113","author":"J Esparza","year":"2011","unstructured":"Esparza, J., Leucker, M., Schlund, M.: Learning workflow Petri nets. Fund. Inform. 113(3\u20134), 205\u2013228 (2011). https:\/\/doi.org\/10.3233\/FI-2011-607","journal-title":"Fund. Inform."},{"key":"9758_CR27","doi-asserted-by":"publisher","unstructured":"Ferreira, T., Brewton, H., D\u2019Antoni, L., Silva, A.: Prognosis: Closed-box analysis of network protocol implementations. In: Proceedings of the 2021 ACM SIGCOMM 2021 Conference, pp. 762\u2013774. ACM, New York, NY, USA (2021). https:\/\/doi.org\/10.1145\/3452296.3472938","DOI":"10.1145\/3452296.3472938"},{"key":"9758_CR28","unstructured":"Fiter\u0103u-Bro\u015ftean, P., Jonsson, B., Merget, R., Ruiter, J., Sagonas, K., Somorovsky, J.: Analysis of DTLS implementations using protocol state fuzzing. In: 29th USENIX Security Symposium (USENIX Security 20), pp. 2523\u20132540. USENIX Association, Boston, MA, USA (2020). https:\/\/www.usenix.org\/conference\/usenixsecurity20\/presentation\/fiterau-brostean"},{"key":"9758_CR29","doi-asserted-by":"crossref","unstructured":"Fiter\u0103u-Bro\u015ftean, P., Jonsson, B., Sagonas, K., T\u00e5quist, F.: Automata-based automated detection of state machine bugs in protocol implementations. In: Network and Distributed System Security Symposium. NDSS 2023. The Internet Society, San Diego, CA, USA (2023). https:\/\/www.ndss-symposium.org\/wp-content\/uploads\/2023\/02\/ndss2023_s68_paper.pdf","DOI":"10.14722\/ndss.2023.23068"},{"key":"9758_CR30","doi-asserted-by":"publisher","unstructured":"Fiter\u0103u-Bro\u015ftean, P., Jonsson, B., Sagonas, K., T\u00e5quist, F.: DTLS-Fuzzer: A DTLS protocol state fuzzer. In: 15th IEEE Conference on Software Testing, Verification and Validation. ICST 2022, pp. 456\u2013458. IEEE, Valencia, Spain (2022). https:\/\/doi.org\/10.1109\/ICST53961.2022.00051","DOI":"10.1109\/ICST53961.2022.00051"},{"key":"9758_CR31","doi-asserted-by":"publisher","unstructured":"Fiter\u0103u-Bro\u015ftean, P., Howar, F.: Learning-based testing the sliding window behavior of TCP implementations. In: Critical Systems: Formal Methods and Automated Verification - Joint 22nd International Workshop on Formal Methods for Industrial Critical Systems - and - 17th International Workshop on Automated Verification of Critical Systems, FMICS-AVoCS. LNCS, vol. 10471, pp. 185\u2013200. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-67113-0_12","DOI":"10.1007\/978-3-319-67113-0_12"},{"key":"9758_CR32","doi-asserted-by":"publisher","unstructured":"Fiter\u0103u-Bro\u015ftean, P., Janssen, R., Vaandrager, F.: Combining model learning and model checking to analyze TCP implementations. In: Chaudhuri, S., Farzan, A. (eds.) Computer Aided Verification. LNCS, vol. 9780, pp. 454\u2013471. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-41540-6_25","DOI":"10.1007\/978-3-319-41540-6_25"},{"key":"9758_CR33","doi-asserted-by":"publisher","unstructured":"Fiter\u0103u-Bro\u015ftean, P., Lenaerts, T., Poll, E., Ruiter, J., Vaandrager, F., Verleg, P.: Model learning and model checking of SSH implementations. In: Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software, pp. 142\u2013151. ACM, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3092282.3092289","DOI":"10.1145\/3092282.3092289"},{"key":"9758_CR34","doi-asserted-by":"crossref","unstructured":"Frank, F., Milius, S., Rot, J., Urbat, H.: Learning Automata with Name Allocation (2025). arXiv:2502.11947","DOI":"10.1109\/LICS65433.2025.00012"},{"key":"9758_CR35","doi-asserted-by":"publisher","unstructured":"Frohme, M., Steffen, B.: Never-stop context-free learning. In: Olderog, E.-R., Steffen, B., Yi, W. (eds.) Model Checking, Synthesis, and Learning. LNCS, vol. 13030, pp. 164\u2013185. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-91384-7_9","DOI":"10.1007\/978-3-030-91384-7_9"},{"issue":"4","key":"9758_CR36","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s10009-021-00634-y","volume":"23","author":"M Frohme","year":"2021","unstructured":"Frohme, M., Steffen, B.: Compositional learning of mutually recursive procedural systems. Int. J. Softw. Tools Technol. Transfer 23(4), 521\u2013543 (2021). https:\/\/doi.org\/10.1007\/s10009-021-00634-y","journal-title":"Int. J. Softw. Tools Technol. Transfer"},{"key":"9758_CR37","doi-asserted-by":"publisher","unstructured":"Garg, P., L\u00f6ding, C., Madhusudan, P., Neider, D.: Learning universally quantified invariants of linear data structures. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification. LNCS, vol. 8044, pp. 813\u2013829. Springer, Berlin, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39799-8_57","DOI":"10.1007\/978-3-642-39799-8_57"},{"key":"9758_CR38","doi-asserted-by":"publisher","unstructured":"Grinchtein, O., Jonsson, B., Pettersson, P.: Inference of event-recording automata using timed decision trees. In: Baier, C., Hermanns, H. (eds.) CONCUR 2006 \u2013 Concurrency Theory. LNCS, vol. 4137, pp. 435\u2013449. Springer, Berlin, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11817949_29","DOI":"10.1007\/11817949_29"},{"key":"9758_CR39","unstructured":"Groz, R., Oriat, C., Vega, G., Silva\u00a0Sim\u00e3o, A., Foster, M., Walkinshaw, N.: Active inference of extended finite state models of software systems. In: Coste, F., Ouardi, F., Rabusseau, G. (eds.) Proceedings of 16th Edition of the International Conference on Grammatical Inference. Proceedings of Machine Learning Research, vol. 217, pp. 265\u2013269. ML Research Press, Cambridge, MA (2023). https:\/\/proceedings.mlr.press\/v217\/groz23a\/groz23a.pdf"},{"key":"9758_CR40","doi-asserted-by":"publisher","unstructured":"Groz, R., Irfan, M.-N., Oriat, C.: Algorithmic improvements on regular inference of software models and perspectives for security testing. In: Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change. ISoLA 2012. LNCS, vol. 7609, pp. 444\u2013457. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34026-0_33","DOI":"10.1007\/978-3-642-34026-0_33"},{"key":"9758_CR41","doi-asserted-by":"publisher","DOI":"10.1016\/J.JSS.2019.110426","author":"R Groz","year":"2020","unstructured":"Groz, R., Br\u00e9mond, N., Silva Sim\u00e3o, A., Oriat, C.: hW-inference: A heuristic approach to retrieve models through black box testing. J. Syst. Softw. (2020). https:\/\/doi.org\/10.1016\/J.JSS.2019.110426","journal-title":"J. Syst. Softw."},{"key":"9758_CR42","doi-asserted-by":"publisher","unstructured":"Hagerer, A., Hungar, H., Niese, O., Steffen, B.: Model generation by moderated regular extrapolation. In: Kutsche, R.-D., Weber, H. (eds.) Fundamental Approaches to Software Engineering, 5th International Conference, FASE 2002. LNCS, vol. 2306, pp. 80\u201395. Springer, Berlin, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45923-5_6","DOI":"10.1007\/3-540-45923-5_6"},{"issue":"9","key":"9758_CR43","doi-asserted-by":"publisher","first-page":"1332","DOI":"10.1016\/j.patcog.2005.01.003","volume":"38","author":"C Higuera","year":"2005","unstructured":"Higuera, C.: A bibliographical study of grammatical inference. Pattern Recogn. 38(9), 1332\u20131348 (2005). https:\/\/doi.org\/10.1016\/j.patcog.2005.01.003","journal-title":"Pattern Recogn."},{"key":"9758_CR44","doi-asserted-by":"publisher","unstructured":"Howar, F., Steffen, B.: Active automata learning in practice. In: Bennaceur, A., H\u00e4hnle, R., Meinke, K. (eds.) Machine Learning for Dynamic Software Analysis: Potentials and Limits. LNCS, vol. 11026, pp. 123\u2013148. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96562-8_5","DOI":"10.1007\/978-3-319-96562-8_5"},{"key":"9758_CR45","doi-asserted-by":"publisher","unstructured":"Howar, F., Steffen, B.: Active automata learning as black-box search and lazy partition refinement. In: Jansen, N., Stoelinga, M., Bos, P. (eds.) A Journey from Process Algebra Via Timed Automata to Model Learning. LNCS, vol. 13560, pp. 321\u2013338. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15629-8_17","DOI":"10.1007\/978-3-031-15629-8_17"},{"key":"9758_CR46","doi-asserted-by":"publisher","unstructured":"Howar, F., Steffen, B., Jonsson, B., Cassel, S.: Inferring canonical register automata. In: Kuncak, V., Rybalchenko, A. (eds.) Verification, Model Checking, and Abstract Interpretation - 13th International Conference, VMCAI 2012, Proceedings. LNCS, vol. 7148, pp. 251\u2013266. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27940-9_17","DOI":"10.1007\/978-3-642-27940-9_17"},{"key":"9758_CR47","doi-asserted-by":"publisher","unstructured":"Howar, F., Steffen, B., Jonsson, B., Cassel, S.: Inferring canonical register automata. In: Kuncak, V., Rybalchenko, A. (eds.) Verification, Model Checking, and Abstract Interpretation. LNCS, vol. 7148, pp. 251\u2013266. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27940-9_17","DOI":"10.1007\/978-3-642-27940-9_17"},{"key":"9758_CR48","doi-asserted-by":"publisher","unstructured":"Hungar, H., Niese, O., Steffen, B.: Domain-specific optimization in automata learning. In: Computer Aided Verification, 15th International Conference. LNCS, vol. 2725, pp. 315\u2013327 (2003). https:\/\/doi.org\/10.1007\/978-3-540-45069-6_31","DOI":"10.1007\/978-3-540-45069-6_31"},{"key":"9758_CR49","doi-asserted-by":"publisher","unstructured":"Isberner, M., Howar, F., Steffen, B.: The TTT algorithm: A redundancy-free approach to active automata learning. In: Runtime Verification: 5th International Conference, RV 2014, Proceedings. LNCS, vol. 8734, pp. 307\u2013322. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11164-3_26","DOI":"10.1007\/978-3-319-11164-3_26"},{"issue":"2","key":"9758_CR50","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M Kaminski","year":"1994","unstructured":"Kaminski, M., Francez, N.: Finite-memory automata. Theoret. Comput. Sci. 134(2), 329\u2013363 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90242-9","journal-title":"Theoret. Comput. Sci."},{"key":"9758_CR51","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"MJ Kearns","year":"1994","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA (1994)"},{"key":"9758_CR52","doi-asserted-by":"publisher","unstructured":"Linard, A., Higuera, C., Vaandrager, F.: Learning unions of $$k$$-testable languages. In: Mart\u00edn-Vide, C., Okhotin, A., Shapira, D. (eds.) Language and Automata Theory and Applications. LNCS, vol. 11417, pp. 328\u2013339. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-13435-8_24","DOI":"10.1007\/978-3-030-13435-8_24"},{"key":"9758_CR53","doi-asserted-by":"publisher","unstructured":"Lorenzoli, D., Mariani, L., Pezz\u00e8, M.: Automatic generation of software behavioral models. In: Proceedings of the 30th International Conference on Software Engineering. ICSE \u201908, pp. 501\u2013510. ACM, New York, NY, USA (2008). https:\/\/doi.org\/10.1145\/1368088.1368157","DOI":"10.1145\/1368088.1368157"},{"key":"9758_CR54","doi-asserted-by":"publisher","unstructured":"Maler, O., Mens, I.: A generic algorithm for learning symbolic automata from membership queries. In: Aceto, L., Bacci, G., Bacci, G., Ing\u00f3lfsd\u00f3ttir, A., Legay, A., Mardare, R. (eds.) Models, Algorithms, Logics and Tools. LNCS, vol. 10460, pp. 146\u2013169. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63121-9_8","DOI":"10.1007\/978-3-319-63121-9_8"},{"key":"9758_CR55","doi-asserted-by":"publisher","unstructured":"Maler, O., Mens, I.-E.: Learning regular languages over large alphabets. In: Tools and Algorithms for the Construction and Analysis of Systems - 20th International Conference,. LNCS, vol. 8413, pp. 485\u2013499. Springer, Berlin, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54862-8_41","DOI":"10.1007\/978-3-642-54862-8_41"},{"key":"9758_CR56","doi-asserted-by":"publisher","unstructured":"Margaria, T., Niese, O., Raffelt, H., Steffen, B.: Efficient test-based model generation for legacy reactive systems. In: Proceedings of the Ninth IEEE International High-Level Design Validation and Test Workshop, pp. 95\u2013100. IEEE, New York, NY, USA (2004). https:\/\/doi.org\/10.1109\/HLDVT.2004.1431246","DOI":"10.1109\/HLDVT.2004.1431246"},{"key":"9758_CR57","doi-asserted-by":"publisher","unstructured":"Merten, M., Howar, F., Steffen, B., Cassel, S., Jonsson, B.: Demonstrating learning of register automata. In: Flanagan, C., K\u00f6nig, B. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 7214, pp. 466\u2013471. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28756-5_32","DOI":"10.1007\/978-3-642-28756-5_32"},{"key":"9758_CR58","volume-title":"Computation: Finite and Infinite Machines","author":"ML Minsky","year":"1967","unstructured":"Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall Series in Automatic Computation. Prentice-Hall, Englewood Cliffs, NJ (1967)"},{"issue":"PLDI","key":"9758_CR59","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1145\/3729295","volume":"9","author":"M Moeller","year":"2025","unstructured":"Moeller, M., Ferreira, T., Lu, T., Foster, N., Silva, A.: Active learning of symbolic netkat automata. Proc. ACM Program. Lang. 9(PLDI), 1119\u20131142 (2025). https:\/\/doi.org\/10.1145\/3729295","journal-title":"Proc. ACM Program. Lang."},{"key":"9758_CR60","doi-asserted-by":"publisher","unstructured":"Moerman, J., Sammartino, M., Silva, A., Klin, B., Szynwelski, M.: Learning nominal automata. In: Proc. $$44^th$$ ACM Symp. on Principles of Programming Languages. POPL \u201917, pp. 613\u2013625. ACM, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3093333.3009879","DOI":"10.1145\/3093333.3009879"},{"key":"9758_CR61","doi-asserted-by":"publisher","unstructured":"Murawski, A.S., Ramsay, S.J., Tzevelekos, N.: Polynomial-time equivalence testing for deterministic fresh-register automata. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 117, pp. 72\u201317214. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.72","DOI":"10.4230\/LIPIcs.MFCS.2018.72"},{"key":"9758_CR62","doi-asserted-by":"publisher","unstructured":"Neider, D., Smetsers, R., Vaandrager, F.W., Kuppens, H.: Benchmarks for automata learning and conformance testing. In: Models, Mindsets, Meta: The What, the How, and the Why Not? - Essays Dedicated to Bernhard Steffen on the Occasion of His 60th Birthday. LNCS, vol. 11200, pp. 390\u2013416. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-22348-9_23","DOI":"10.1007\/978-3-030-22348-9_23"},{"issue":"3","key":"9758_CR63","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1013560.1013562","volume":"5","author":"F Neven","year":"2004","unstructured":"Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log. 5(3), 403\u2013435 (2004). https:\/\/doi.org\/10.1145\/1013560.1013562","journal-title":"ACM Trans. Comput. Log."},{"key":"9758_CR64","doi-asserted-by":"publisher","unstructured":"Oncina, J., Garc\u00eda, P.: Inferring regular languages in polynomial update time. In: Pattern Recognition and Image Analysis. Series in Machine Perception and Artificial Intelligence, vol. 1, pp. 49\u201361. World Scientific, Singapore (1992). https:\/\/doi.org\/10.1142\/9789812797902_0004","DOI":"10.1142\/9789812797902_0004"},{"issue":"2","key":"9758_CR65","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/inco.1993.1021","volume":"103","author":"RL Rivest","year":"1993","unstructured":"Rivest, R.L., Schapire, R.E.: Inference of finite automata using homing sequences. Inf. Comput. 103(2), 299\u2013347 (1993). https:\/\/doi.org\/10.1006\/inco.1993.1021","journal-title":"Inf. Comput."},{"key":"9758_CR66","unstructured":"Ruiter, J., Poll, E.: Protocol state fuzzing of TLS implementations. In: 24th USENIX Security Symposium (USENIX Security 15), pp. 193\u2013206. USENIX Association, Washington, D.C., USA (2015). https:\/\/www.usenix.org\/conference\/usenixsecurity15\/technical-sessions\/presentation\/de-ruiter"},{"key":"9758_CR67","doi-asserted-by":"publisher","unstructured":"Sagonas, K., Jonsson, B., Howar, F., Dierl, S., Fiter\u0103u-Bro\u015ftean, P., T\u00e5quist, F.: Reproduction Artifact for TACAS 2024 paper \u201cScalable Tree-based Register Automata Learning\u201d (2023). https:\/\/doi.org\/10.5281\/zenodo.10442556","DOI":"10.5281\/zenodo.10442556"},{"key":"9758_CR68","doi-asserted-by":"publisher","unstructured":"Sakamoto, H.: Learning simple deterministic finite-memory automata. In: Algorithmic Learning Theory. ALT \u201997. LNCS, vol. 1316, pp. 416\u2013431. Springer, Berlin, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63577-7_58","DOI":"10.1007\/3-540-63577-7_58"},{"key":"9758_CR69","doi-asserted-by":"publisher","unstructured":"Schuts, M., Hooman, J., Vaandrager, F.: Refactoring of legacy software using model learning and equivalence checking: An industrial experience report. In: \u00c1brah\u00e1m, E., Huisman, M. (eds.) Integrated Formal Methods. LNCS, vol. 9681, pp. 311\u2013325. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-33693-0_20","DOI":"10.1007\/978-3-319-33693-0_20"},{"issue":"4","key":"9758_CR70","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/stvr.1491","volume":"24","author":"M Shahbaz","year":"2014","unstructured":"Shahbaz, M., Groz, R.: Analysis and testing of black-box component-based systems by inferring partial models. Software Testing, Verification and Reliability 24(4), 253\u2013288 (2014). https:\/\/doi.org\/10.1002\/stvr.1491","journal-title":"Software Testing, Verification and Reliability"},{"key":"9758_CR71","doi-asserted-by":"publisher","unstructured":"Shu, G., Lee, D.: Testing security properties of protocol implementations - a machine learning based approach. In: 27th IEEE International Conference on Distributed Computing Systems. ICDCS 2007, p. 25. IEEE Computer Society, Los Alamitos, CA (2007). https:\/\/doi.org\/10.1109\/ICDCS.2007.147","DOI":"10.1109\/ICDCS.2007.147"},{"key":"9758_CR72","doi-asserted-by":"publisher","unstructured":"Sun, J., Xiao, H., Liu, Y., Lin, S.-W., Qin, S.: TLV: abstraction through testing, learning, and validation. In: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, pp. 698\u2013709. ACM, New York, NY, USA (2015). https:\/\/doi.org\/10.1145\/2786805.2786817","DOI":"10.1145\/2786805.2786817"},{"key":"9758_CR73","doi-asserted-by":"publisher","unstructured":"Tappler, M., Aichernig, B.K., Bloem, R.: Model-based testing IoT communication via active automata learning. In: IEEE International Conference on Software Testing, Verification and Validation, pp. 276\u2013287. IEEE Computer Society, Tokyo, Japan (2017). https:\/\/doi.org\/10.1109\/ICST.2017.32","DOI":"10.1109\/ICST.2017.32"},{"issue":"2","key":"9758_CR74","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/2967606","volume":"60","author":"FW Vaandrager","year":"2017","unstructured":"Vaandrager, F.W.: Model learning. Commun. ACM 60(2), 86\u201395 (2017). https:\/\/doi.org\/10.1145\/2967606","journal-title":"Commun. ACM"},{"key":"9758_CR75","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2022.01.015","volume":"912","author":"FW Vaandrager","year":"2022","unstructured":"Vaandrager, F.W., Midya, A.: A Myhill-Nerode theorem for register automata and symbolic trace languages. Theor. Comput. Sci. 912, 37\u201355 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.01.015","journal-title":"Theor. Comput. Sci."},{"key":"9758_CR76","doi-asserted-by":"publisher","unstructured":"Vaandrager, F., Bloem, R., Ebrahimi, M.: Learning Mealy machines with one timer. In: Leporati, A., Mart\u00edn-Vide, C., Shapira, D., Zandron, C. (eds.) Language and Automata Theory and Applications. LNCS, vol. 12638, pp. 157\u2013170. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-68195-1_13","DOI":"10.1007\/978-3-030-68195-1_13"},{"key":"9758_CR77","doi-asserted-by":"publisher","unstructured":"Vaandrager, F., Garhewal, B., Rot, J., Wi\u00dfmann, T.: A new approach for active automata learning based on apartness. In: Fisman, D., Rosu, G. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 13243, pp. 223\u2013243. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-99524-9_12","DOI":"10.1007\/978-3-030-99524-9_12"},{"key":"9758_CR78","doi-asserted-by":"publisher","unstructured":"Volpato, M., Tretmans, J.: Active learning of nondeterministic systems from an ioco perspective. In: Margaria, T., Steffen, B. (eds.) Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change. LNCS, vol. 8802, pp. 220\u2013235. Springer, Berlin, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45234-9_16","DOI":"10.1007\/978-3-662-45234-9_16"},{"key":"9758_CR79","doi-asserted-by":"publisher","unstructured":"Walkinshaw, N., Bogdanov, K., Derrick, J., Par\u00eds, J.: Increasing functional coverage by inductive testing: A case study. In: Testing Software and Systems - 22nd IFIP WG 6.1 International Conference, ICTSS 2010. LNCS, vol. 6435, pp. 126\u2013141. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16573-3_10","DOI":"10.1007\/978-3-642-16573-3_10"}],"container-title":["Journal of Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-026-09758-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10817-026-09758-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-026-09758-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T09:04:07Z","timestamp":1785747847000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10817-026-09758-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,3]]},"references-count":79,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["9758"],"URL":"https:\/\/doi.org\/10.1007\/s10817-026-09758-9","relation":{},"ISSN":["0168-7433","1573-0670"],"issn-type":[{"value":"0168-7433","type":"print"},{"value":"1573-0670","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,3]]},"assertion":[{"value":"25 May 2026","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"14"}}