{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T22:56:52Z","timestamp":1768431412672,"version":"3.49.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["448468041"],"award-info":[{"award-number":["448468041"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>We propose a scalable framework for deciding, proving, and explaining (in-)equivalence of context-free grammars. We present an implementation of the framework and evaluate it on large data sets collected within educational support systems. Even though the equivalence problem for context-free languages is undecidable in general, the framework is able to handle a large portion of these datasets. It introduces and combines techniques from several areas, such as an abstract grammar transformation language to identify equivalent grammars as well as sufficiently similar inequivalent grammars, theory-based comparison algorithms for a large class of context-free languages, and a graph-theory-inspired grammar canonization that allows to efficiently identify isomorphic grammars.<\/jats:p>","DOI":"10.1145\/3763156","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:51:31Z","timestamp":1759999891000},"page":"2954-2980","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Detecting and Explaining (In-)equivalence of Context-Free Grammars"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3966-6590","authenticated-orcid":false,"given":"Marko","family":"Schmellenkamp","sequence":"first","affiliation":[{"name":"Ruhr University Bochum, Bochum, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5186-7507","authenticated-orcid":false,"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[{"name":"Ruhr University Bochum, Bochum, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5544-6417","authenticated-orcid":false,"given":"Sven","family":"Argo","sequence":"additional","affiliation":[{"name":"Ruhr University Bochum, Bochum, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4614-9444","authenticated-orcid":false,"given":"Sandra","family":"Kiefer","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5671-2209","authenticated-orcid":false,"given":"Cedric","family":"Siems","sequence":"additional","affiliation":[{"name":"Ruhr University Bochum, Bochum, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1352-7892","authenticated-orcid":false,"given":"Fynn","family":"Stebel","sequence":"additional","affiliation":[{"name":"Ruhr University Bochum, Bochum, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence","author":"Alur Rajeev","year":"2013","unstructured":"Rajeev Alur, Loris D\u2019Antoni, Sumit Gulwani, Dileep Kini, and Mahesh Viswanathan. 2013. Automated Grading of DFA Constructions. IJCAI\/AAAI, In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. isbn:978-1-57735-633-2 1976-1982. https:\/\/www.microsoft.com\/en-us\/research\/publication\/automated-grading-dfa-constructions\/"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/00091383.2012.728955"},{"key":"e_1_2_1_3_1","volume-title":"Generation CS: Computer Science Undergraduate Enrollments Surge Since","author":"Computing Research Association","year":"2017","unstructured":"Computing Research Association. 2017. Generation CS: Computer Science Undergraduate Enrollments Surge Since 2006. cra.org. http:\/\/cra.org\/data\/generation-cs"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08918-8_10"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53291-8_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723163"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649409.3691070"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007441"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197091.3197095"},{"key":"e_1_2_1_11_1","unstructured":"Gesellschaft f\u00fcr Informatik e. V. 2016. Empfehlungen f\u00fcr Bachelor- und Master-Programme im Studienfach Informatik an Hochschulen. gi.de. https:\/\/dl.gi.de\/handle\/20.500.12116\/2351"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/1994067"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/299649.299800"},{"key":"e_1_2_1_14_1","unstructured":"Julien Grange Fabian Vehlken Nils Vortmeier and Thomas Zeume. 2024. Specification and Automatic Verification of Computational Reductions. MFCS."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.18420\/infos2019-c6"},{"key":"e_1_2_1_16_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"1979","unstructured":"John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley. isbn:0-201-02988-X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80038-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19754-3_16"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.13"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641554.3701967"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3664191"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11219-010-9116-5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21350-2_18"},{"key":"e_1_2_1_24_1","unstructured":"Josje Lodder Bastiaan Heeren and Johan Jeuring. 2015. A pilot study of the use of LogEx lessons learned. CoRR abs\/1507.03671 1507.03671."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814304"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55602-8_160"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48199-0_14"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"e_1_2_1_29_1","unstructured":"Moj\u017cesz Presburger. 1929. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen in welchen die Addition als einzige Operation hervortritt. In Comptes Rendus Premier Congr\u00e8s des Math\u00e9maticienes des Pays Slaves. 92-101."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/337885.337896"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89439-1_20"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Marko Schmellenkamp. 2025. Student attempts for context-free grammar construction tasks. Zenodo. doi:10.5281\/zenodo.16921093 10.5281\/zenodo.16921093","DOI":"10.5281\/zenodo.16921093"},{"key":"e_1_2_1_33_1","unstructured":"Marko Schmellenkamp Fabian Vehlken and Thomas Zeume. 2024. Teaching Formal Foundations of Computer Science with Iltis. Bull. EATCS 142 http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/797"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Marko Schmellenkamp Thomas Zeume Sven Argo Sandra Kiefer Cedric Siems and Fynn Stebel. 2025. Artifact for paper: Detecting and Explaining (In-)equivalence of Context-Free Grammars. Zenodo. doi:10.5281\/zenodo.16921238 10.5281\/zenodo.16921238","DOI":"10.5281\/zenodo.16921238"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Marko Schmellenkamp Thomas Zeume Sven Argo Sandra Kiefer Cedric Siems and Fynn Stebel. 2025. Detecting and Explaining (In-)equivalence of Context-Free Grammars. Full version doi:10.48550\/arXiv.2407.18220 10.48550\/arXiv.2407.18220","DOI":"10.48550\/arXiv.2407.18220"},{"key":"e_1_2_1_36_1","volume-title":"Schweingruber","author":"Singer Susan R.","year":"2012","unstructured":"Susan R. Singer, Natalie R. Nielsen, and Heidi A. Schweingruber. 2012. Discipline-based education research."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11532231_25"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523732"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:44:19Z","timestamp":1760031859000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":38,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763156"],"URL":"https:\/\/doi.org\/10.1145\/3763156","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}