{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T03:37:16Z","timestamp":1768448236296,"version":"3.49.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,1,16]]},"abstract":"<jats:p>We consider grammar-restricted exact learning of formulas and terms in finite variable logics. We propose a novel and versatile automata-theoretic technique for solving such problems. We first show results for learning formulas that classify a set of positively- and negatively-labeled structures. We give algorithms for realizability and synthesis of such formulas along with upper and lower bounds. We also establish positive results using our technique for other logics and variants of the learning problem, including first-order logic with least fixed point definitions, higher-order logics, and synthesis of queries and terms with recursively-defined functions.<\/jats:p>","DOI":"10.1145\/3498671","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T17:03:12Z","timestamp":1642006992000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Learning formulas in finite variable logics"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6710-9516","authenticated-orcid":false,"given":"Paul","family":"Krogmeier","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9782-721X","authenticated-orcid":false,"given":"P.","family":"Madhusudan","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66158-2_44"},{"key":"e_1_2_2_2_1","volume-title":"Dependable Software Systems Engineering (NATO Science for Peace and Security Series, D: Information and Communication Security","author":"Alur Rajeev","unstructured":"Rajeev Alur , Rastislav Bod\u00edk , Eric Dallal , Dana Fisman , Pranav Garg , Garvit Juniwal , Hadas Kress-Gazit , P. Madhusudan , Milo M. K. Martin , Mukund Raghothaman , Shambwaditya Saha , Sanjit A. Seshia , Rishabh Singh , Armando Solar-Lezama , Emina Torlak , and Abhishek Udupa . 2015. Syntax-Guided Synthesis . In Dependable Software Systems Engineering (NATO Science for Peace and Security Series, D: Information and Communication Security , Vol. 40). IOS Press, 1\u2013 25 . Rajeev Alur, Rastislav Bod\u00edk, Eric Dallal, Dana Fisman, Pranav Garg, Garvit Juniwal, Hadas Kress-Gazit, P. Madhusudan, Milo M. K. Martin, Mukund Raghothaman, Shambwaditya Saha, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2015. Syntax-Guided Synthesis. In Dependable Software Systems Engineering (NATO Science for Peace and Security Series, D: Information and Communication Security, Vol. 40). IOS Press, 1\u201325."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.08.007"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0280205-0"},{"key":"e_1_2_2_5_1","volume-title":"What\u2019s Decidable about Syntax-Guided Synthesis? CoRR, abs\/1510.08393","author":"Caulfield Benjamin","year":"2015","unstructured":"Benjamin Caulfield , Markus N. Rabe , Sanjit A. Seshia , and Stavros Tripakis . 2015. What\u2019s Decidable about Syntax-Guided Synthesis? CoRR, abs\/1510.08393 ( 2015 ), arxiv:1510.08393 Benjamin Caulfield, Markus N. Rabe, Sanjit A. Seshia, and Stavros Tripakis. 2015. What\u2019s Decidable about Syntax-Guided Synthesis? CoRR, abs\/1510.08393 (2015), arxiv:1510.08393"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462180"},{"key":"e_1_2_2_7_1","first-page":"30","article-title":"Application of recursive arithmetic to the problem of circuit synthesis. Summaries of talks presented at the Summer Institute for Symbolic Logic Cornell University, 1957, 2nd edn","volume":"28","author":"Church Alonzo","year":"1960","unstructured":"Alonzo Church . 1960 . Application of recursive arithmetic to the problem of circuit synthesis. Summaries of talks presented at the Summer Institute for Symbolic Logic Cornell University, 1957, 2nd edn ., Journal of Symbolic Logic , 28 , 4 (1960), 30 \u2013 50 . 3a\u201345a.. Alonzo Church. 1960. Application of recursive arithmetic to the problem of circuit synthesis. Summaries of talks presented at the Summer Institute for Symbolic Logic Cornell University, 1957, 2nd edn., Journal of Symbolic Logic, 28, 4 (1960), 30\u201350. 3a\u201345a..","journal-title":"Journal of Symbolic Logic"},{"key":"e_1_2_2_8_1","unstructured":"H. Comon M. Dauchet R. Gilleron C. L\u00f6ding F. Jacquemard D. Lugiez S. Tison and M. Tommasi. 2007. Tree Automata Techniques and Applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata. release October 12th 2007.  H. Comon M. Dauchet R. Gilleron C. L\u00f6ding F. Jacquemard D. Lugiez S. Tison and M. Tommasi. 2007. Tree Automata Techniques and Applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata. release October 12th 2007."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/673"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31485-8_3"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-08-049646-7.50008-4"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241691.3241692"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4_20"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/233"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-015-0231-6"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 28th International Conference on Algorithmic Learning Theory, Steve Hanneke and Lev Reyzin (Eds.) (Proceedings of Machine Learning Research","volume":"451","author":"Grohe Martin","year":"2017","unstructured":"Martin Grohe , Christof L\u00f6ding , and Martin Ritzert . 2017 . Learning MSO-definable hypotheses on strings . In Proceedings of the 28th International Conference on Algorithmic Learning Theory, Steve Hanneke and Lev Reyzin (Eds.) (Proceedings of Machine Learning Research , Vol. 76). PMLR, Kyoto University, Kyoto, Japan. 434\u2013 451 . http:\/\/proceedings.mlr.press\/v76\/grohe17a.html Martin Grohe, Christof L\u00f6ding, and Martin Ritzert. 2017. Learning MSO-definable hypotheses on strings. In Proceedings of the 28th International Conference on Algorithmic Learning Theory, Steve Hanneke and Lev Reyzin (Eds.) (Proceedings of Machine Learning Research, Vol. 76). PMLR, Kyoto University, Kyoto, Japan. 434\u2013451. http:\/\/proceedings.mlr.press\/v76\/grohe17a.html"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1112-8"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25540-4_18"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385979"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802187"},{"key":"e_1_2_2_27_1","volume-title":"Logical Separability of Incomplete Data under Ontologies. CoRR, abs\/2007.01610","author":"Jung Jean Christoph","year":"2020","unstructured":"Jean Christoph Jung , Carsten Lutz , Hadrien Pulcini , and Frank Wolter . 2020. Logical Separability of Incomplete Data under Ontologies. CoRR, abs\/2007.01610 ( 2020 ), arxiv:2007.01610 Jean Christoph Jung, Carsten Lutz, Hadrien Pulcini, and Frank Wolter. 2020. Logical Separability of Incomplete Data under Ontologies. CoRR, abs\/2007.01610 (2020), arxiv:2007.01610"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01090-4_29"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386018"},{"key":"e_1_2_2_30_1","unstructured":"Paul Krogmeier and P. Madhusudan. 2021. Learning Formulas in Finite Variable Logics. arxiv:2111.03534.  Paul Krogmeier and P. Madhusudan. 2021. Learning Formulas in Finite Variable Logics. arxiv:2111.03534."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53291-8_32"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44618-4_9"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13754-9_11"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11558-0_22"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2011.428"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_33"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/357084.357090"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290359"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(82)90040-6"},{"key":"e_1_2_2_41_1","volume-title":"Machine Learning (1 ed.)","author":"Mitchell Thomas M.","unstructured":"Thomas M. Mitchell . 1997. Machine Learning (1 ed.) . McGraw-Hill, Inc. , USA. isbn:0070428077 Thomas M. Mitchell. 1997. Machine Learning (1 ed.). McGraw-Hill, Inc., USA. isbn:0070428077"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90035-3"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5358-3"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2018.8603016"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738007"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89597"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908093"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_2_2_50_1","volume-title":"Automata on Infinite Objects and Church\u2019s Problem","author":"Rabin Michael Oser","year":"1816","unstructured":"Michael Oser Rabin . 1972. Automata on Infinite Objects and Church\u2019s Problem . American Mathematical Society, Boston, MA , USA. isbn:082 1816 632 https:\/\/dl.acm.org\/doi\/10.5555\/540412 Michael Oser Rabin. 1972. Automata on Infinite Objects and Church\u2019s Problem. American Mathematical Society, Boston, MA, USA. isbn:0821816632 https:\/\/dl.acm.org\/doi\/10.5555\/540412"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593664"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454098"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785811"},{"key":"e_1_2_2_55_1","volume-title":"On the Parameterized Complexity of Learning Logic. CoRR, abs\/2102.12201","author":"van Bergerem Steffen","year":"2021","unstructured":"Steffen van Bergerem , Martin Grohe , and Martin Ritzert . 2021. On the Parameterized Complexity of Learning Logic. CoRR, abs\/2102.12201 ( 2021 ), arxiv:2102.12201. Steffen van Bergerem, Martin Grohe, and Martin Ritzert. 2021. On the Parameterized Complexity of Learning Logic. CoRR, abs\/2102.12201 (2021), arxiv:2102.12201."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055090"},{"key":"e_1_2_2_58_1","unstructured":"Victor Vianu. 2020. Personal communication.  Victor Vianu. 2020. Personal communication."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062365"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133886"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276525"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498671","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498671","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:28Z","timestamp":1750188628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498671"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":61,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2022,1,16]]}},"alternative-id":["10.1145\/3498671"],"URL":"https:\/\/doi.org\/10.1145\/3498671","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"assertion":[{"value":"2022-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}