{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:19:17Z","timestamp":1781075957545,"version":"3.54.1"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030995232","type":"print"},{"value":"9783030995249","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"vor","delay-in-days":88,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a new learning algorithm for realtime one-counter automata. Our algorithm uses membership and equivalence queries as in Angluin\u2019s <jats:inline-formula><jats:alternatives><jats:tex-math>$${L}^*$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>L<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mo>\u2217<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> algorithm, as well as counter value queries and partial equivalence queries. In a partial equivalence query, we ask the teacher whether the language of a given finite-state automaton coincides with a counter-bounded subset of the target language. We evaluate an implementation of our algorithm on a number of random benchmarks and on a use case regarding efficient JSON-stream validation.<\/jats:p>","DOI":"10.1007\/978-3-030-99524-9_13","type":"book-chapter","created":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T06:14:55Z","timestamp":1648534495000},"page":"244-262","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Learning Realtime One-Counter Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9680-9140","authenticated-orcid":false,"given":"V\u00e9ronique","family":"Bruy\u00e8re","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1200-4952","authenticated-orcid":false,"given":"Guillermo A.","family":"P\u00e9rez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5795-3265","authenticated-orcid":false,"given":"Ga\u00ebtan","family":"Staquet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","unstructured":"Aarts, F., Jonsson, B., Uijen, J., Vaandrager, F.W.: Generating models of infinite-state communication protocols using regular inference with abstraction. Formal Methods Syst. Des. 46(1), 1\u201341 (2015). https:\/\/doi.org\/10.1007\/s10703-014-0216-x","DOI":"10.1007\/s10703-014-0216-x"},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Abel, A., Reineke, J.: Gray-box learning of serial compositions of mealy machines. In: Rayadurgam, S., Tkachuk, O. (eds.) NASA Formal Methods - 8th International Symposium, NFM 2016, Minneapolis, MN, USA, June 7-9, 2016, Proceedings. Lecture Notes in Computer Science, vol.\u00a09690, pp. 272\u2013287. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-40648-0_21","DOI":"10.1007\/978-3-319-40648-0_21"},{"key":"13_CR3","unstructured":"Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley series in computer science\/World student series edition, Addison-Wesley (1986), https:\/\/www.worldcat.org\/oclc\/12285707"},{"key":"13_CR4","doi-asserted-by":"publisher","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","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"13_CR5","doi-asserted-by":"publisher","unstructured":"Baazizi, M.A., Colazzo, D., Ghelli, G., Sartiani, C.: Schemas and types for JSON data. In: Herschel, M., Galhardas, H., Reinwald, B., Fundulaki, I., Binnig, C., Kaoudi, Z. (eds.) Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26-29, 2019. pp. 437\u2013439. OpenProceedings.org (2019). https:\/\/doi.org\/10.5441\/002\/edbt.2019.39","DOI":"10.5441\/002\/edbt.2019.39"},{"key":"13_CR6","doi-asserted-by":"publisher","unstructured":"Berman, P., Roos, R.: Learning one-counter languages in polynomial time (extended abstract). In: 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987. pp. 61\u201367. IEEE Computer Society (1987). https:\/\/doi.org\/10.1109\/SFCS.1987.36","DOI":"10.1109\/SFCS.1987.36"},{"key":"13_CR7","doi-asserted-by":"publisher","unstructured":"Berthon, R., Boiret, A., P\u00e9rez, G.A., Raskin, J.: Active learning of sequential transducers with side information about the domain. In: Moreira, N., Reis, R. (eds.) Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12811, pp. 54\u201365. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-81508-0_5","DOI":"10.1007\/978-3-030-81508-0_5"},{"key":"13_CR8","doi-asserted-by":"publisher","unstructured":"B\u00f6hm, S., G\u00f6ller, S., Jancar, P.: Bisimulation equivalence and regularity for real-time one-counter automata. J. Comput. Syst. Sci. 80(4), 720\u2013743 (2014). https:\/\/doi.org\/10.1016\/j.jcss.2013.11.003","DOI":"10.1016\/j.jcss.2013.11.003"},{"key":"13_CR9","doi-asserted-by":"publisher","unstructured":"Bollig, B.: One-counter automata with counter observability. In: Lal, A., Akshay, S., Saurabh, S., Sen, S. (eds.) 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India. LIPIcs, vol.\u00a065, pp. 20:1\u201320:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2016.20","DOI":"10.4230\/LIPIcs.FSTTCS.2016.20"},{"key":"13_CR10","doi-asserted-by":"publisher","unstructured":"Bouajjani, A., Bozga, M., Habermehl, P., Iosif, R., Moro, P., Vojnar, T.: Programs with lists are counter automata. Formal Methods Syst. Des. 38(2), 158\u2013192 (2011). https:\/\/doi.org\/10.1007\/s10703-011-0111-7","DOI":"10.1007\/s10703-011-0111-7"},{"key":"13_CR11","doi-asserted-by":"publisher","unstructured":"Bray, T.: The javascript object notation (JSON) data interchange format. RFC 8259, 1\u201316 (2017). https:\/\/doi.org\/10.17487\/RFC8259","DOI":"10.17487\/RFC8259"},{"key":"13_CR12","unstructured":"Bruy\u00e8re, V., P\u00e9rez, G.A., Staquet, G.: Learning realtime one-counter automata. CoRR abs\/2110.09434 (2021), https:\/\/arxiv.org\/abs\/2110.09434"},{"key":"13_CR13","doi-asserted-by":"publisher","unstructured":"Chitic, C., Rosu, D.: On validation of XML streams using finite state machines. In: Amer-Yahia, S., Gravano, L. (eds.) Proceedings of the Seventh International Workshop on the Web and Databases, WebDB 2004, June 17-18, 2004, Maison de la Chimie, Paris, France, Colocated with ACM SIGMOD\/PODS 2004. pp. 85\u201390. ACM (2004). https:\/\/doi.org\/10.1145\/1017074.1017096","DOI":"10.1145\/1017074.1017096"},{"key":"13_CR14","unstructured":"Codecov, https:\/\/about.codecov.io\/"},{"key":"13_CR15","doi-asserted-by":"publisher","unstructured":"Fahmy, A.F., Roos, R.S.: Efficient learning of real time one-counter automata. In: Jantke, K.P., Shinohara, T., Zeugmann, T. (eds.) Algorithmic Learning Theory, 6th International Conference, ALT \u201995, Fukuoka, Japan, October 18-20, 1995, Proceedings. Lecture Notes in Computer Science, vol.\u00a0997, pp. 25\u201340. Springer (1995). https:\/\/doi.org\/10.1007\/3-540-60454-5_26","DOI":"10.1007\/3-540-60454-5_26"},{"key":"13_CR16","doi-asserted-by":"publisher","unstructured":"Garhewal, B., Vaandrager, F.W., Howar, F., Schrijvers, T., Lenaerts, T., Smits, R.: Grey-box learning of register automata. In: Dongol, B., Troubitsyna, E. (eds.) Integrated Formal Methods - 16th International Conference, IFM 2020, Lugano, Switzerland, November 16-20, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12546, pp. 22\u201340. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-63461-2_2","DOI":"10.1007\/978-3-030-63461-2_2"},{"key":"13_CR17","doi-asserted-by":"publisher","unstructured":"Groce, A., Peled, D.A., Yannakakis, M.: Adaptive model checking. Log. J. IGPL 14(5), 729\u2013744 (2006). https:\/\/doi.org\/10.1093\/jigpal\/jzl007","DOI":"10.1093\/jigpal\/jzl007"},{"key":"13_CR18","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, Second Edition. Addison-Wesley (2000)"},{"key":"13_CR19","doi-asserted-by":"publisher","unstructured":"Isberner, M., Howar, F., Steffen, B.: The TTT algorithm: A redundancy-free approach to active automata learning. In: Bonakdarpour, B., Smolka, S.A. (eds.) Runtime Verification - 5th International Conference, RV 2014, Toronto, ON, Canada, September 22-25, 2014. Proceedings. Lecture Notes in Computer Science, vol.\u00a08734, pp. 307\u2013322. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-11164-3_26","DOI":"10.1007\/978-3-319-11164-3_26"},{"key":"13_CR20","doi-asserted-by":"publisher","unstructured":"Isberner, M., Howar, F., Steffen, B.: The open-source learnlib - A framework for active automata learning. In: Kroening, D., Pasareanu, C.S. (eds.) Computer Aided Verification - 27th International Conference, CAV 2015, San Francisco, CA, USA, July 18-24, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol.\u00a09206, pp. 487\u2013495. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-21690-4_32","DOI":"10.1007\/978-3-319-21690-4_32"},{"key":"13_CR21","unstructured":"Json.org, https:\/\/www.json.org"},{"key":"13_CR22","unstructured":"Json schema, https:\/\/json-schema.org"},{"key":"13_CR23","unstructured":"Json schema store, https:\/\/www.schemastore.org\/json\/"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press (1994), https:\/\/mitpress.mit.edu\/books\/introduction-computational-learning-theory","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Leucker, M., Neider, D.: Learning minimal deterministic automata from inexperienced teachers. In: Margaria, T., Steffen, B. (eds.) Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change - 5th International Symposium, ISoLA 2012, Heraklion, Crete, Greece, October 15-18, 2012, Proceedings, Part I. Lecture Notes in Computer Science, vol.\u00a07609, pp. 524\u2013538. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-34026-0_39","DOI":"10.1007\/978-3-642-34026-0_39"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Michaliszyn, J., Otop, J.: Learning deterministic automata on infinite words. In: Giacomo, G.D., Catal\u00e1, A., Dilkina, B., Milano, M., Barro, S., Bugar\u00edn, A., Lang, J. (eds.) ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020). Frontiers in Artificial Intelligence and Applications, vol.\u00a0325, pp. 2370\u20132377. IOS Press (2020). https:\/\/doi.org\/10.3233\/FAIA200367","DOI":"10.3233\/FAIA200367"},{"key":"13_CR27","unstructured":"Neider, D., L\u00f6ding, C.: Learning visibly one-counter automata in polynomial time. Tech. rep., Technical Report AIB-2010-02, RWTH Aachen (January 2010) (2010)"},{"key":"13_CR28","doi-asserted-by":"publisher","unstructured":"Peled, D.A., Vardi, M.Y., Yannakakis, M.: Black box checking. J. Autom. Lang. Comb. 7(2), 225\u2013246 (2002). https:\/\/doi.org\/10.25596\/jalc-2002-225","DOI":"10.25596\/jalc-2002-225"},{"key":"13_CR29","doi-asserted-by":"publisher","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","DOI":"10.1006\/inco.1993.1021"},{"key":"13_CR30","unstructured":"Roos, R.S.: Deciding equivalence of deterministic one-counter automata in polynomial time with applications to learning (1988)"},{"key":"13_CR31","unstructured":"Staquet, G.: Automatalib fork for rocas, https:\/\/github.com\/DocSkellington\/automatalib"},{"key":"13_CR32","unstructured":"Staquet, G.: Code for the benchmarks for roca learning, https:\/\/github.com\/DocSkellington\/LStar-ROCA-Benchmarks"},{"key":"13_CR33","unstructured":"Staquet, G.: Learnlib fork for rocas, https:\/\/github.com\/DocSkellington\/Learnlib"},{"key":"13_CR34","doi-asserted-by":"publisher","unstructured":"Valiant, L.G., Paterson, M.: Deterministic one-counter automata. J. Comput. Syst. Sci. 10(3), 340\u2013350 (1975). https:\/\/doi.org\/10.1016\/S0022-0000(75)80005-5","DOI":"10.1016\/S0022-0000(75)80005-5"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-99524-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T06:21:59Z","timestamp":1648534919000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-99524-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030995232","9783030995249"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-99524-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"30 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 April 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2022\/tacas","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":"159","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":"46","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":"4","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":"29% - 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":"10","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":"16 tool papers of the affiliated competition SV-Comp and 1 paper consisting of the competition report are also included in the proceedings","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)"}}]}}