{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:14:13Z","timestamp":1771697653900,"version":"3.50.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030720155","type":"print"},{"value":"9783030720162","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":78,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present an algorithm for extracting a subclass of the context free grammars (CFGs) from a trained recurrent neural network (RNN). We develop a new framework,<jats:italic>pattern rule sets<\/jats:italic>(PRSs), which describe sequences of deterministic finite automata (DFAs) that approximate a non-regular language. We present an algorithm for recovering the PRS behind a sequence of such automata, and apply it to the sequences of automata extracted from trained RNNs using the<jats:inline-formula><jats:alternatives><jats:tex-math>$$L^{*}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>L<\/mml:mi><mml:mrow><mml:mrow\/><mml:mo>\u2217<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>algorithm. We then show how the PRS may converted into a CFG, enabling a familiar and useful presentation of the learned language.<\/jats:p><jats:p>Extracting the learned language of an RNN is important to facilitate understanding of the RNN and to verify its correctness. Furthermore, the extracted CFG can augment the RNN in classifying correct sentences, as the RNN\u2019s predictive accuracy decreases when the recursion depth and distance between matching delimiters of its input sequences increases.<\/jats:p>","DOI":"10.1007\/978-3-030-72016-2_19","type":"book-chapter","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T22:03:37Z","timestamp":1616191417000},"page":"351-369","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Synthesizing Context-free Grammars from Recurrent Neural Networks"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7214-5610","authenticated-orcid":false,"given":"Daniel M.","family":"Yellin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0762-9090","authenticated-orcid":false,"given":"Gail","family":"Weiss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Inductive inference of formal languages from positive data. Inf. Control. 45(2), 117\u2013135 (1980), https:\/\/doi.org\/10.1016\/S0019-9958(80)90285-5","DOI":"10.1016\/S0019-9958(80)90285-5"},{"key":"19_CR2","doi-asserted-by":"crossref","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":"19_CR3","unstructured":"Ayache, S., Eyraud, R., Goudian, N.: Explaining black boxes on sequential data using weighted automata. In: Unold, O., Dyrka, W., Wieczorek, W. (eds.) Proceedings of the 14th International Conference on Grammatical Inference, ICGI 2018. Proceedings of Machine Learning Research, vol.\u00a093, pp. 81\u2013103. PMLR (2018), http:\/\/proceedings.mlr.press\/v93\/ayache19a.html"},{"key":"19_CR4","unstructured":"Bahdanau, D., Cho, K., Bengio, Y.: Neural machine translation by jointly learning to align and translate. In: Bengio, Y., LeCun, Y. (eds.) 3rd International Conference on Learning Representations, ICLR 2015 (2015), http:\/\/arxiv.org\/abs\/1409.0473"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Bernardy, J.P.: Can recurrent neural networks learn nested recursion? In: Linguistic Issues in Language Technology, Volume 16, 2018. CSLI Publications (2018), https:\/\/www.aclweb.org\/anthology\/2018.lilt-16.1","DOI":"10.33011\/lilt.v16i.1417"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Cechin, A.L., Simon, D.R.P., Stertz, K.: State automata extraction from recurrent neural nets using k-means and fuzzy clustering. In: 23rd International Conference of the Chilean Computer Science Society (SCCC 2003). pp. 73\u201378. IEEE Computer Society (2003). https:\/\/doi.org\/10.1109\/SCCC.2003.1245447","DOI":"10.1109\/SCCC.2003.1245447"},{"key":"19_CR7","unstructured":"Clark, A., Eyraud, R.: Polynomial identification in the limit of substitutable context-free languages. J. Mach. Learn. Res. 8, 1725\u20131745 (2007), http:\/\/dl.acm.org\/citation.cfm?id=1314556"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Clark, A., Eyraud, R., Habrard, A.: A polynomial algorithm for the inference of context free languages. In: Clark, A., Coste, F., Miclet, L. (eds.) Grammatical Inference: Algorithms and Applications, 9th International Colloquium, ICGI 2008, Proceedings. Lecture Notes in Computer Science, vol.\u00a05278, pp. 29\u201342. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-88009-7_3","DOI":"10.1007\/978-3-540-88009-7_3"},{"key":"19_CR9","unstructured":"Das, S., Giles, C.L., Sun, G.: Learning context-free grammars: Capabilities and limitations of a recurrent neural network with an external stack memory. In: Conference of the Cognitive Science Society. pp. 791\u2013795. Morgan Kaufmann Publishers (1992)"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"D\u2019Ulizia, A., Ferri, F., Grifoni, P.: A survey of grammatical inference methods for natural language learning. Artif. Intell. Rev. 36(1), 1\u201327 (2011). https:\/\/doi.org\/10.1007\/s10462-010-9199-1","DOI":"10.1007\/s10462-010-9199-1"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Gold, E.M.: Language identification in the limit. Information and Control 10(5), 447\u2013474 (May 1967), https:\/\/doi.org\/10.1016\/S0019-9958(67)91165-5","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"19_CR12","unstructured":"Hailesilassie, T.: Rule extraction algorithm for deep neural networks: A review. International Journal of Computer Science and Information Security (IJCSIS) 14(7) (July 2016)"},{"key":"19_CR13","unstructured":"Hewitt, J., Hahn, M., Ganguli, S., Liang, P., Manning, C.D.: RNNs can generate bounded hierarchical languages with optimal memory. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 1978\u20132010. Association for Computational Linguistics (2020), https:\/\/www.aclweb.org\/anthology\/2020.emnlp-main.156"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural Computation 9(8), 1735\u20131780 (1997). https:\/\/doi.org\/10.1162\/neco.1997.9.8.1735","DOI":"10.1162\/neco.1997.9.8.1735"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Jacobsson, H.: Rule extraction from recurrent neural networks: A taxonomy and review. Neural Computation 17(6), 1223\u20131263 (2005). https:\/\/doi.org\/10.1162\/0899766053630350","DOI":"10.1162\/0899766053630350"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Kozen, D.C.: The Chomsky\u2014Sch\u00fctzenberger theorem. In: Automata and Computability. pp. 198\u2013200. Springer Berlin Heidelberg, Berlin, Heidelberg (1977)","DOI":"10.1007\/978-3-642-85706-5_34"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Luong, T., Pham, H., Manning, C.D.: Effective approaches to attention-based neural machine translation. In: M\u00e0rquez, L., Callison-Burch, C., Su, J., Pighin, D., Marton, Y. (eds.) Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015. pp. 1412\u20131421. The Association for Computational Linguistics (2015). https:\/\/doi.org\/10.18653\/v1\/d15-1166","DOI":"10.18653\/v1\/D15-1166"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Omlin, C.W., Giles, C.L.: Extraction of rules from discrete-time recurrent neural networks. Neural Networks 9(1), 41\u201352 (1996). https:\/\/doi.org\/10.1016\/0893-6080(95)00086-0","DOI":"10.1016\/0893-6080(95)00086-0"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Sennhauser, L., Berwick, R.: Evaluating the ability of LSTMs to learn context-free grammars. In: Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP. pp. 115\u2013124. Association for Computational Linguistics (Nov 2018). https:\/\/doi.org\/10.18653\/v1\/W18-5414","DOI":"10.18653\/v1\/W18-5414"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Siegelmann, H.T., Sontag, E.D.: On the Computational Power of Neural Nets. J. Comput. Syst. Sci. 50(1), 132\u2013150 (1995). https:\/\/doi.org\/10.1006\/jcss.1995.1013","DOI":"10.1006\/jcss.1995.1013"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Skachkova, N., Trost, T., Klakow, D.: Closing brackets with recurrent neural networks. In: Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP. pp. 232\u2013239. Association for Computational Linguistics (Nov 2018). https:\/\/doi.org\/10.18653\/v1\/W18-5425","DOI":"10.18653\/v1\/W18-5425"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Stevenson, A., Cordy, J.R.: A survey of grammatical inference in software engineering. Sci. Comput. Program. 96(P4), 444\u2013459 (Dec 2014). https:\/\/doi.org\/10.1016\/j.scico.2014.05.008","DOI":"10.1016\/j.scico.2014.05.008"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Sun, G., Giles, C.L., Chen, H.: The neural network pushdown automaton: Architecture, dynamics and training. In: Giles, C.L., Gori, M. (eds.) Adaptive Processing of Sequences and Data Structures, International Summer School on Neural Networks. Lecture Notes in Computer Science, vol.\u00a01387, pp. 296\u2013345. Springer (1997). https:\/\/doi.org\/10.1007\/BFb0054003","DOI":"10.1007\/BFb0054003"},{"key":"19_CR24","unstructured":"Thrun, S.: Extracting rules from artifical neural networks with distributed representations. In: Tesauro, G., Touretzky, D.S., Leen, T.K. (eds.) Advances in Neural Information Processing Systems 7, NIPS Conference, 1994. pp. 505\u2013512. MIT Press (1994), http:\/\/papers.nips.cc\/paper\/924-extracting-rules-from-artificial-neural-networks-with-distributed-representations"},{"key":"19_CR25","unstructured":"Wang, Q., Zhang, K., Liu, X., Giles, C.L.: Connecting first and second order recurrent networks with deterministic finite automata. CoRR abs\/1911.04644 (2019), http:\/\/arxiv.org\/abs\/1911.04644"},{"key":"19_CR26","unstructured":"Weiss, G., Goldberg, Y., Yahav, E.: Extracting automata from recurrent neural networks using queries and counterexamples. In: Dy, J.G., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning, ICML 2018. Proceedings of Machine Learning Research, vol.\u00a080, pp. 5244\u20135253. PMLR (2018), http:\/\/proceedings.mlr.press\/v80\/weiss18a.html"},{"key":"19_CR27","unstructured":"Yellin, D.M., Weiss, G.: Synthesizing context-free grammars from recurrent neural networks (extended version) (2021), http:\/\/arxiv.org\/abs\/2101.08200"},{"key":"19_CR28","unstructured":"Yu, X., Vu, N.T., Kuhn, J.: Learning the Dyck language with attention-based Seq2Seq models. In: Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP. pp. 138\u2013146. Association for Computational Linguistics (2019), https:\/\/www.aclweb.org\/anthology\/W19-4815"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-72016-2_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T01:02:51Z","timestamp":1671670971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-72016-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030720155","9783030720162"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-72016-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 March 2021","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":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/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":"141","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":"41","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":"21","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":"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 changed to an online format due to the COVID-19 pandemic","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)"}}]}}