{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T20:57:20Z","timestamp":1760043440136,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T00:00:00Z","timestamp":1680739200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2021ZD0110202"],"award-info":[{"award-number":["2021ZD0110202"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62161146003"],"award-info":[{"award-number":["62161146003"]}],"id":[{"id":"10.13039\/501100001809","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":[[2023,4,6]]},"abstract":"<jats:p>Oracle-guided inductive synthesis (OGIS) is a widely-used framework to apply program synthesis techniques in practice. The question selection problem aims at reducing the number of iterations in OGIS by selecting a proper input for each OGIS iteration. Theoretically, a question selector can generally improve the performance of OGIS solvers on both interactive and non-interactive tasks if it is not only effective for reducing iterations but also efficient. However, all existing effective question selectors fail in satisfying the requirement of efficiency. To ensure effectiveness, they convert the question selection problem into an optimization one, which is difficult to solve within a short time.<\/jats:p>\n          <jats:p>\n            In this paper, we propose a novel question selector, named\n            <jats:italic>LearnSy<\/jats:italic>\n            .\n            <jats:italic>LearnSy<\/jats:italic>\n            is both efficient and effective and thus achieves general improvement for OGIS solvers for the first time. Since we notice that the optimization tasks in previous studies are difficult because of the complex behavior of operators, we estimate these behaviors in\n            <jats:italic>LearnSy<\/jats:italic>\n            as simple random events. Subsequently, we provide theoretical results for the precision of this estimation and design an efficient algorithm for its calculation.\n          <\/jats:p>\n          <jats:p>\n            According to our evaluation, when dealing with interactive tasks,\n            <jats:italic>LearnSy<\/jats:italic>\n            can offer competitive performance compared to existing selectors while being more efficient and more general. Moreover, when working on non-interactive tasks,\n            <jats:italic>LearnSy<\/jats:italic>\n            can generally reduce the time cost of existing CEGIS solvers by up to 43.0%.\n          <\/jats:p>","DOI":"10.1145\/3586055","type":"journal-article","created":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T21:06:02Z","timestamp":1680815162000},"page":"819-847","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Improving Oracle-Guided Inductive Synthesis by Efficient Question Selection"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0150-8629","authenticated-orcid":false,"given":"Ruyi","family":"Ji","sequence":"first","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8232-8680","authenticated-orcid":false,"given":"Chaozhe","family":"Kong","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8991-747X","authenticated-orcid":false,"given":"Yingfei","family":"Xiong","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9034-205X","authenticated-orcid":false,"given":"Zhenjiang","family":"Hu","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9510-9"},{"key":"e_1_2_1_2_1","volume-title":"FMCAD 2013","author":"Alur Rajeev","year":"2013","unstructured":"Rajeev Alur , Rastislav Bod\u00edk , Garvit Juniwal , Milo M. K. Martin , Mukund Raghothaman , Sanjit A. Seshia , Rishabh Singh , Armando Solar-Lezama , Emina Torlak , and Abhishek Udupa . 2013 . Syntax-guided synthesis. In Formal Methods in Computer-Aided Design , FMCAD 2013 , Portland, OR, USA , October 20-23, 2013. 1\u20138. http:\/\/ieeexplore.ieee.org\/document\/6679385\/ Rajeev Alur, Rastislav Bod\u00edk, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2013. Syntax-guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD 2013, Portland, OR, USA, October 20-23, 2013. 1\u20138. http:\/\/ieeexplore.ieee.org\/document\/6679385\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.260.9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814228.2814235"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90114-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921661"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72016-2_9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568250"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_33"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-017-0294-5"},{"key":"e_1_2_1_14_1","unstructured":"Ruyi Ji Chaozhe Kong Yingfei Xiong and Zhenjiang Hu. 2023. Artifact for OOPSLA\u201923: Improving Oracle-Guided Inductive Synthesis by Efficient Question Selection. https:\/\/github.com\/jiry17\/LearnSy \t\t\t\t  Ruyi Ji Chaozhe Kong Yingfei Xiong and Zhenjiang Hu. 2023. Artifact for OOPSLA\u201923: Improving Oracle-Guided Inductive Synthesis by Efficient Question Selection. https:\/\/github.com\/jiry17\/LearnSy"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7722241"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386025"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428292"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485544"},{"key":"e_1_2_1_19_1","volume-title":"6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. https:\/\/openreview.net\/forum?id=rywDjg-RW","author":"Kalyan Ashwin","year":"2018","unstructured":"Ashwin Kalyan , Abhishek Mohta , Oleksandr Polozov , Dhruv Batra , Prateek Jain , and Sumit Gulwani . 2018 . Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples . In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. https:\/\/openreview.net\/forum?id=rywDjg-RW Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. 2018. Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. https:\/\/openreview.net\/forum?id=rywDjg-RW"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978942.1979444"},{"key":"e_1_2_1_21_1","unstructured":"Vipin Kumar Ananth Grama Anshul Gupta and George Karypis. 1994. Introduction to parallel computing. 110 Benjamin\/Cummings Redwood City CA. \t\t\t\t  Vipin Kumar Ananth Grama Anshul Gupta and George Karypis. 1994. Introduction to parallel computing. 110 Benjamin\/Cummings Redwood City CA."},{"key":"e_1_2_1_22_1","volume-title":"Interactive Program Synthesis. CoRR, abs\/1703.03539","author":"Le Vu","year":"2017","unstructured":"Vu Le , Daniel Perelman , Oleksandr Polozov , Mohammad Raza , Abhishek Udupa , and Sumit Gulwani . 2017. Interactive Program Synthesis. CoRR, abs\/1703.03539 ( 2017 ), arXiv:1703.03539. arxiv:1703.03539 Vu Le, Daniel Perelman, Oleksandr Polozov, Mohammad Raza, Abhishek Udupa, and Sumit Gulwani. 2017. Interactive Program Synthesis. CoRR, abs\/1703.03539 (2017), arXiv:1703.03539. arxiv:1703.03539"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192410"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738002"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807442.2807459"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397481.3450680"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276520"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3324884.3416613"},{"key":"e_1_2_1_30_1","volume-title":"Inferring LISP Programs From Examples. In Advance Papers of the Fourth International Joint Conference on Artificial Intelligence","author":"Shaw David E.","year":"1975","unstructured":"David E. Shaw , William R. Swartout , and C. Cordell Green . 1975 . Inferring LISP Programs From Examples. In Advance Papers of the Fourth International Joint Conference on Artificial Intelligence , Tbilisi, Georgia, USSR , September 3-8, 1975 . 260\u2013267. http:\/\/ijcai.org\/Proceedings\/75\/Papers\/037.pdf David E. Shaw, William R. Swartout, and C. Cordell Green. 1975. Inferring LISP Programs From Examples. In Advance Papers of the Fourth International Joint Conference on Artificial Intelligence, Tbilisi, Georgia, USSR, September 3-8, 1975. 260\u2013267. http:\/\/ijcai.org\/Proceedings\/75\/Papers\/037.pdf"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_23"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_1_33_1","volume-title":"Information-theoretic User Interaction: Significant Inputs for Program Synthesis. CoRR, abs\/2006.12638","author":"Tiwari Ashish","year":"2020","unstructured":"Ashish Tiwari , Arjun Radhakrishna , Sumit Gulwani , and Daniel Perelman . 2020. Information-theoretic User Interaction: Significant Inputs for Program Synthesis. CoRR, abs\/2006.12638 ( 2020 ), arXiv:2006.12638. arxiv:2006.12638 Ashish Tiwari, Arjun Radhakrishna, Sumit Gulwani, and Daniel Perelman. 2020. Information-theoretic User Interaction: Significant Inputs for Program Synthesis. CoRR, abs\/2006.12638 (2020), arXiv:2006.12638. arxiv:2006.12638"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3058738"},{"key":"e_1_2_1_35_1","unstructured":"Henry S Warren. 2002. Hacker\u2019s Delight. \t\t\t\t  Henry S Warren. 2002. Hacker\u2019s Delight."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501988.2502040"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586055","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3586055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:10Z","timestamp":1750183690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,6]]},"references-count":36,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2023,4,6]]}},"alternative-id":["10.1145\/3586055"],"URL":"https:\/\/doi.org\/10.1145\/3586055","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2023,4,6]]},"assertion":[{"value":"2023-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}