{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:16:25Z","timestamp":1746159385113,"version":"3.40.4"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031913976","type":"print"},{"value":"9783031913983","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-91398-3_31","type":"book-chapter","created":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T22:06:50Z","timestamp":1746137210000},"page":"419-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Extracting Moore Machines from\u00a0Transformers Using Queries and\u00a0Counterexamples"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-7863-4034","authenticated-orcid":false,"given":"Rik","family":"Adriaensen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9474-6150","authenticated-orcid":false,"given":"Jaron","family":"Maene","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,2]]},"reference":[{"key":"31_CR1","unstructured":"Ackerman, J., Cybenko, G.: A survey of neural networks and formal languages. arXiv preprint arXiv:2006.01338 (2020)"},{"issue":"2","key":"31_CR2","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)","journal-title":"Inf. Comput."},{"issue":"4","key":"31_CR3","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1023\/A:1022821128753","volume":"2","author":"D Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1988). https:\/\/doi.org\/10.1023\/A:1022821128753","journal-title":"Mach. Learn."},{"issue":"2","key":"31_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF00992675","volume":"9","author":"D Angluin","year":"1992","unstructured":"Angluin, D., Frazier, M., Pitt, L.: Learning conjunctions of horn clauses. Mach. Learn. 9(2), 147\u2013164 (1992)","journal-title":"Mach. Learn."},{"key":"31_CR5","first-page":"38546","volume":"35","author":"C Anil","year":"2022","unstructured":"Anil, C., et al.: Exploring length generalization in large language models. Adv. Neural. Inf. Process. Syst. 35, 38546\u201338556 (2022)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Balle, B., Mohri, M.: Learning weighted automata, pp. 1\u201321 (2015)","DOI":"10.1007\/978-3-319-23021-4_1"},{"issue":"3","key":"31_CR7","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"D Barrington","year":"1992","unstructured":"Barrington, D., Compton, K., Straubing, H., Th\u00e9rien, D.: Regular languages in nc1. J. Comput. Syst. Sci. 44(3), 478\u2013499 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Bhattamishra, S., Ahuja, K., Goyal, N.: On the ability and limitations of transformers to recognize formal languages. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7096\u20137116. Association for Computational Linguistics (2020)","DOI":"10.18653\/v1\/2020.emnlp-main.576"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Blum, S., Koudijs, R., Ozaki, A., Touileb, S.: Learning horn envelopes via queries from language models. Int. J. Approximate Reasoning 171, 109026 (2024). synergies between Machine Learning and Reasoning","DOI":"10.1016\/j.ijar.2023.109026"},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"Chiang, D., Cholak, P.: Overcoming a theoretical limitation of self-attention. In: Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (2022)","DOI":"10.18653\/v1\/2022.acl-long.527"},{"key":"31_CR11","unstructured":"Del\u00e9tang, G., et al.: Neural networks and the chomsky hierarchy. In: The Eleventh International Conference on Learning Representations (2022)"},{"issue":"6","key":"31_CR12","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1109\/72.963769","volume":"12","author":"F Gers","year":"2001","unstructured":"Gers, F., Schmidhuber, E.: Lstm recurrent networks learn simple context-free and context-sensitive languages. IEEE Trans. Neural Netw. 12(6), 1333\u20131340 (2001)","journal-title":"IEEE Trans. Neural Netw."},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Giles, C.L., Miller, C.B., Chen, D., Sun, G.Z., Chen, H.H., Lee, Y.C.: Extracting and learning an unknown grammar with recurrent neural networks. In: Moody, J., Hanson, S., Lippmann, R. (eds.) Advances in Neural Information Processing Systems, vol.\u00a04. Morgan-Kaufmann (1991)","DOI":"10.1162\/neco.1992.4.3.393"},{"issue":"3","key":"31_CR14","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"EM Gold","year":"1978","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Inf. Control 37(3), 302\u2013320 (1978). https:\/\/doi.org\/10.1016\/S0019-9958(78)90562-4","journal-title":"Inf. Control"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Hahn, M., Rofin, M.: Why are sensitive functions hard for transformers? . In: Ku, L.W., Martins, A., Srikumar, V. (eds.) Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 14973\u201315008. Association for Computational Linguistics, Bangkok, Thailand (2024). 10.18653\/v1\/2024.acl-long.800","DOI":"10.18653\/v1\/2024.acl-long.800"},{"key":"31_CR16","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2006","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley Longman Publishing Co., Inc, USA (2006)","edition":"3"},{"key":"31_CR17","unstructured":"Kingma, D.P., Ba, J.L.: Adam: a method for stochastic gradient descent. In: International Conference on Learning Representations, pp. 1\u201315 (2015)"},{"key":"31_CR18","unstructured":"Liu, B., Ash, J.T., Goel, S., Krishnamurthy, A., Zhang, C.: Transformers learn shortcuts to automata. In: The Eleventh International Conference on Learning Representations (2023)"},{"key":"31_CR19","unstructured":"Merrill, W.: Formal language theory meets modern nlp. arXiv preprint arXiv:2102.10094 (2021)"},{"key":"31_CR20","unstructured":"Moerman, J.: Learning product automata. In: Unold, O., Dyrka, W., Wieczorek, W. (eds.) Proceedings of Machine Learning Research, vol.\u00a093, pp. 54\u201366. PMLR (2019)"},{"key":"31_CR21","unstructured":"Nguyen, T.Q., Salazar, J.: Transformers without tears: Improving the normalization of self-attention. In: Niehues, J., et al., (eds.) Proceedings of the 16th International Conference on Spoken Language Translation. Association for Computational Linguistics, Hong Kong (2019)"},{"key":"31_CR22","unstructured":"Strobl, L., Merrill, W., Weiss, G., Chiang, D., Angluin, D.: Transformers as recognizers of formal languages: a survey on expressivity (2023)"},{"key":"31_CR23","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2023.127063","volume":"568","author":"J Su","year":"2024","unstructured":"Su, J., Ahmed, M., Lu, Y., Pan, S., Bo, W., Liu, Y.: Roformer: enhanced transformer with rotary position embedding. Neurocomputing 568, 127063 (2024)","journal-title":"Neurocomputing"},{"key":"31_CR24","unstructured":"Suzgun, M., Belinkov, Y., Shieber, S.M.: On evaluating the generalization of lstm models in formal languages, pp. 277\u2013286 (2019)"},{"key":"31_CR25","unstructured":"Vaswani, A., et al.: Attention is all you need. In: Guyon, I., et al., (eds.) Advances in Neural Information Processing Systems, vol.\u00a030. Curran Associates, Inc. (2017)"},{"key":"31_CR26","unstructured":"Weiss, G., Goldberg, Y., Yahav, E.: Extracting automata from recurrent neural networks using queries and counterexamples. In: International Conference on Machine Learning, pp. 5247\u20135256. PMLR (2018)"},{"key":"31_CR27","unstructured":"Weiss, G., Goldberg, Y., Yahav, E.: Learning deterministic weighted automata with queries and counterexamples. In: Wallach, H., Larochelle, H., Beygelzimer, A., d\u2019 Alch\u00e9-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol.\u00a032. Curran Associates, Inc. (2019)"},{"key":"31_CR28","unstructured":"Yang, A., Chiang, D., Angluin, D.: Masked hard-attention transformers recognize exactly the star-free languages (2023)"},{"key":"31_CR29","doi-asserted-by":"crossref","unstructured":"Yao, S., Peng, B., Papadimitriou, C., Narasimhan, K.: Self-attention networks can process bounded hierarchical languages. In: Zong, C., Xia, F., Li, W., Navigli, R. (eds.) Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, vol. 1, pp. 3770\u20133785. Association for Computational Linguistics, Online (2021)","DOI":"10.18653\/v1\/2021.acl-long.292"},{"key":"31_CR30","unstructured":"Zhang, Y., Wei, Z., Sun, M.: Automata extraction from transformers (2024)"}],"container-title":["Lecture Notes in Computer Science","Advances in Intelligent Data Analysis XXIII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91398-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T22:07:09Z","timestamp":1746137229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91398-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031913976","9783031913983"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91398-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"2 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IDA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Intelligent Data Analysis","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Konstanz","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":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 May 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 May 2025","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":"ida2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ida2025.blogs.dsv.su.se\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}