{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:20:31Z","timestamp":1784830831259,"version":"3.55.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1919197, 2046071, 2319425, 2332891"],"award-info":[{"award-number":["1919197, 2046071, 2319425, 2332891"]}],"id":[{"id":"10.13039\/100000001","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,6,10]]},"abstract":"<jats:p>\n                    Program synthesis aims at the automatic generation of programs based on given specifications. Despite significant progress, the inherent complexity of synthesis tasks and the interplay among intention, invention and adaptation limit its scope. A promising yet challenging avenue is the integration of concurrency to enhance synthesis algorithms. While some efforts have applied basic concurrency by parallelizing search spaces, more intricate synthesis scenarios involving interdependent subproblems remain unexplored. In this paper, we focus on string transformation as the target domain and introduce the first concurrent synthesis algorithm that enables asynchronous coordination between deductive and enumerative processes, featuring an asynchronous deducer for dynamic task decomposition, a versatile enumerator for resolving enumeration requests, and an accumulative case splitter for if-then-else condition\/branch search and assembling. Our implementation,\n                    <jats:sc>Synthphonia<\/jats:sc>\n                    exhibits substantial performance improvements over state-of-the-art synthesizers, successfully solving 116 challenging string transformation tasks for the first time.\n                  <\/jats:p>","DOI":"10.1145\/3729336","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"2131-2155","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Concurrent Approach to String Transformation Synthesis"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-9941-6394","authenticated-orcid":false,"given":"Yuantian","family":"Ding","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9476-7349","authenticated-orcid":false,"given":"Xiaokang","family":"Qiu","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Aws Albarghouthi Sumit Gulwani and Zachary Kincaid. 2013. Recursive Program Synthesis. In Computer Aided Verification. Natasha Sharygina and Helmut Veith (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 934\u2013950.","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Rajeev Alur Arjun Radhakrishna and Abhishek Udupa. 2017. Scaling Enumerative Program Synthesis via Divide and Conquer. In Tools and Algorithms for the Construction and Analysis of Systems. Axel Legay and Tiziana Margaria (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 319\u2013336.","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_3_2_4_2","article-title":"DeepCoder: Learning to Write Programs","author":"Balog Matej","year":"2017","unstructured":"Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2017. DeepCoder: Learning to Write Programs. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=ByldLrqlx","journal-title":"International Conference on Learning Representations"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Haniel Barbosa Clark Barrett Martin Brain Gereon Kremer Hanna Lachnitt Makai Mann Abdalrhman Mohamed Mudathir Mohamed Aina Niemetz Andres N\u00f6tzli Alex Ozdemir Mathias Preiner Andrew Reynolds Ying Sheng Cesare Tinelli and Yoni Zohar. 2022. cvc5: A Versatile and Industrial-Strength SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems. Dana Fisman and Grigore Rosu (Eds.). Springer International Publishing Cham 415\u2013442.","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428295"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"Clark Barrett Christopher L. Conway Morgan Deters Liana Hadarean Dejan Jovanovi\u0107 Tim King Andrew Reynolds and Cesare Tinelli. 2011. CVC4. In Computer Aided Verification. Ganesh Gopalakrishnan and Shaz Qadeer (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 171\u2013177.","DOI":"10.1007\/978-3-642-22110-1_14"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","unstructured":"James Bornholt Emina Torlak Dan Grossman and Luis Ceze. 2016. Optimizing Synthesis with Metasketches. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (St. Petersburg FL USA) (POPL \u201916). Association for Computing Machinery New York NY USA 775\u2013788. https:\/\/doi.org\/10.1145\/2837614.2837666 10.1145\/2837614.2837666","DOI":"10.1145\/2837614.2837666"},{"key":"e_1_3_2_9_2","article-title":"Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis","author":"Bunel Rudy","year":"2018","unstructured":"Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. 2018. Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis. In International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=H1Xw62kRZ","journal-title":"International Conference on Learning Representations"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571226"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158091"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"Benjamin Delaware Cl\u00e9ment Pit-Claudel Jason Gross and Adam Chlipala. 2015. Fiat: Deductive Synthesis of Abstract Data Types in a Proof Assistant. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Mumbai India) (POPL \u201915). Association for Computing Machinery New York NY USA 689\u2013700. https:\/\/doi.org\/10.1145\/2676726.2677006 10.1145\/2676726.2677006","DOI":"10.1145\/2676726.2677006"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","unstructured":"Yuantian Ding. 2025. Artifact for the Paper \"A Concurrent Approach to String Transformation Synthesis\". https:\/\/doi.org\/10.5281\/zenodo.15249631 10.5281\/zenodo.15249631","DOI":"10.5281\/zenodo.15249631"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632913"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","unstructured":"Yu Feng Ruben Martins Osbert Bastani and Isil Dillig. 2018. Program Synthesis Using Conflict-driven Learning. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (Philadelphia PA USA) (PLDI 2018). ACM New York NY USA 420\u2013435. https:\/\/doi.org\/10.1145\/3192366.3192382 10.1145\/3192366.3192382","DOI":"10.1145\/3192366.3192382"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","unstructured":"Yu Feng Ruben Martins Jacob Van Geffen Isil Dillig and Swarat Chaudhuri. 2017. Component-based Synthesis of Table Consolidation and Transformation Tasks from Examples. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (Barcelona Spain) (PLDI 2017). ACM New York NY USA 422\u2013436. https:\/\/doi.org\/10.1145\/3062341.3062351 10.1145\/3062341.3062351","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","unstructured":"John K. Feser Swarat Chaudhuri and Isil Dillig. 2015. Synthesizing Data Structure Transformations from Input-Output Examples. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (Portland OR USA) (PLDI 2015). Association for Computing Machinery New York NY USA 229\u2013239. https:\/\/doi.org\/10.1145\/2737924.2737977 10.1145\/2737924.2737977","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3211346.3211355"},{"key":"e_1_3_2_19_2","unstructured":"Irene Gloria Greif. 1975. Semantics of Communicating Parallel Processes. PhD dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Sumit Gulwani. 2011. Automating String Processing in Spreadsheets Using Input-output Examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Austin Texas USA) (POPL \u201911). ACM New York NY USA 317\u2013330. https:\/\/doi.org\/10.1145\/1926385.1926423 10.1145\/1926385.1926423","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_3_2_21_2","unstructured":"Carl Hewitt. 1976. Viewing Control Structures as Patterns of Passing Messages. Technical Report AIM-410. MIT Artificial Intelligence Laboratory. http:\/\/dspace.mit.edu\/handle\/1721.1\/6272"},{"key":"e_1_3_2_22_2","unstructured":"Carl Hewitt Peter Bishop and Richard Steiger. 1973. A universal modular ACTOR formalism for artificial intelligence. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence (Stanford USA) (IJCAI \u201973). Morgan Kaufmann Publishers Inc. San Francisco CA USA 235\u00e2\u0102\u015e245. http:\/\/ijcai.org\/Proceedings\/73\/Papers\/027B.pdf"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Kangjing Huang Xiaokang Qiu Peiyuan Shen and Yanjun Wang. 2020. Reconciling Enumerative and Deductive Program Synthesis. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London UK) (PLDI 2020). Association for Computing Machinery New York NY USA 1159\u20131174. https:\/\/doi.org\/10.1145\/3385412.3386027 10.1145\/3385412.3386027","DOI":"10.1145\/3385412.3386027"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"Jinseong Jeon Xiaokang Qiu Armando Solar-Lezama and Jeffrey S. Foster. 2015. Adaptive Concretization for Parallel Program Synthesis. In Computer Aided Verification Daniel Kroening and Corina S. P\u0103s\u0103reanu (Eds.). Springer International Publishing Cham 377\u2013394.","DOI":"10.1007\/978-3-319-21668-3_22"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-017-0269-8"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485544"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Etienne Kneuss Ivan Kuraj Viktor Kuncak and Philippe Suter. 2013. Synthesis Modulo Recursive Functions. In OOPSLA\u201913 (Indianapolis Indiana USA). ACM 407\u2013426.","DOI":"10.1145\/2509136.2509555"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434335"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","unstructured":"Woosuk Lee Kihong Heo Rajeev Alur and Mayur Naik. 2018. Accelerating Search-based Program Synthesis Using Learned Probabilistic Models. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (Philadelphia PA USA) (PLDI 2018). ACM New York NY USA 436\u2013449. https:\/\/doi.org\/10.1145\/3192366.3192410 10.1145\/3192366.3192410","DOI":"10.1145\/3192366.3192410"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3408991"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3408991"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234198"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/357084.357090"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5522"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","unstructured":"Andres N\u00f6tzli Andrew Reynolds Haniel Barbosa Aina Niemetz Mathias Preiner Clark Barrett and Cesare Tinelli. 2019. Syntax-Guided Rewrite Rule Enumeration for SMT Solvers. In Theory and Applications of Satisfiability Testing \u2013 SAT 2019 Mikol\u00e1\u0161 Janota and In\u00eas Lynce (Eds.). Springer International Publishing Cham 279\u2013297.","DOI":"10.1007\/978-3-030-24258-9_20"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","unstructured":"Oleksandr Polozov and Sumit Gulwani. 2015. FlashMeta: A Framework for Inductive Program Synthesis. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems Languages and Applications (Pittsburgh PA USA) (OOPSLA 2015). Association for Computing Machinery New York NY USA 107\u2013126. https:\/\/doi.org\/10.1145\/2814270.2814310 10.1145\/2814270.2814310","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_3_2_37_2","article-title":"PROSE public benchmark suite","author":"Microsoft PROSE","year":"2022","unstructured":"Microsoft PROSE. 2022. PROSE public benchmark suite. Github. https:\/\/github.com\/microsoft\/prose-benchmarks","journal-title":"Github"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840306"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116251"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","unstructured":"Abhishek Udupa Arun Raghavan Jyotirmoy V. Deshmukh Sela Mador-Haim Milo M.K. Martin and Rajeev Alur. 2013. TRANSIT: Specifying Protocols with Concolic Snippets. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (Seattle Washington USA) (PLDI \u201913). Association for Computing Machinery New York NY USA 287\u00e2\u0102\u015e296. https:\/\/doi.org\/10.1145\/2491956.2462174 10.1145\/2491956.2462174","DOI":"10.1145\/2491956.2462174"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591274"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591288"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729336","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:04:47Z","timestamp":1784196287000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":41,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729336"],"URL":"https:\/\/doi.org\/10.1145\/3729336","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}