{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T20:00:27Z","timestamp":1790798427909,"version":"4.1.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1712060, 1453386"],"award-info":[{"award-number":["1712060, 1453386"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["8750-14-2-0270"],"award-info":[{"award-number":["8750-14-2-0270"]}],"id":[{"id":"10.13039\/100006602","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":[[2018,1]]},"abstract":"<jats:p>\n            We present a new approach to example-guided program synthesis based on\n            <jats:italic>counterexample-guided abstraction refinement<\/jats:italic>\n            . Our method uses the abstract semantics of the underlying DSL to find a program\n            <jats:italic>P<\/jats:italic>\n            whose\n            <jats:italic>abstract<\/jats:italic>\n            behavior satisfies the examples. However, since program\n            <jats:italic>P<\/jats:italic>\n            may be spurious with respect to the concrete semantics, our approach iteratively refines the abstraction until we either find a program that satisfies the examples or prove that no such DSL program exists. Because many programs have the same input-output behavior in terms of their\n            <jats:italic>abstract semantics<\/jats:italic>\n            , this synthesis methodology significantly reduces the search space compared to existing techniques that use purely concrete semantics.\n          <\/jats:p>\n          <jats:p>\n            While\n            <jats:italic>synthesis using abstraction refinement (SYNGAR)<\/jats:italic>\n            could be implemented in different settings, we propose a refinement-based synthesis algorithm that uses\n            <jats:italic>abstract finite tree automata (AFTA)<\/jats:italic>\n            . Our technique uses a coarse initial program abstraction to construct an initial AFTA, which is iteratively refined by constructing a\n            <jats:italic>proof of incorrectness<\/jats:italic>\n            of any spurious program. In addition to ruling out the spurious program accepted by the previous AFTA, proofs of incorrectness are also useful for ruling out many other spurious programs.\n          <\/jats:p>\n          <jats:p>We implement these ideas in a framework called Blaze, which can be instantiated in different domains by providing a suitable DSL and its corresponding concrete and abstract semantics. We have used the Blaze framework to build synthesizers for string and matrix transformations, and we compare Blaze with existing techniques. Our results for the string domain show that Blaze compares favorably with FlashFill, a domain-specific synthesizer that is now deployed in Microsoft PowerShell. In the context of matrix manipulations, we compare Blaze against Prose, a state-of-the-art general-purpose VSA-based synthesizer, and show that Blaze results in a 90x speed-up over Prose. In both application domains, Blaze also consistently improves upon the performance of two other existing techniques by at least an order of magnitude.<\/jats:p>","DOI":"10.1145\/3158151","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":65,"title":["Program synthesis using abstraction refinement"],"prefix":"10.1145","volume":"2","author":[{"given":"Xinyu","family":"Wang","sequence":"first","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Isil","family":"Dillig","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rishabh","family":"Singh","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70844-5_22"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958031.2958069"},{"key":"e_1_2_2_3_1","first-page":"1","article-title":"Syntax-guided synthesis","volume":"40","author":"Alur Rajeev","year":"2015","journal-title":"Dependable Software Systems Engineering"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Rajeev Alur Dana Fisman Rishabh Singh and Armando Solar-Lezama. 2016. SyGuS-Comp 2016: Results and Analysis. In SYNT. 178\u2013202.  Rajeev Alur Dana Fisman Rishabh Singh and Armando Solar-Lezama. 2016. SyGuS-Comp 2016: Results and Analysis. In SYNT. 178\u2013202.","DOI":"10.4204\/EPTCS.229.13"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1965724.1965743"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3220881.3220981"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398507"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_2_10_1","volume-title":"RobustFill: Neural Program Learning under Noisy I\/O. arXiv preprint arXiv:1703.07469","author":"Devlin Jacob","year":"2017"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837629"},{"key":"e_1_2_2_14_1","volume-title":"Abstract interpretation over non-deterministic finite tree automata for set-based analysis of logic programs. Practical Aspects of Declarative Languages","author":"Gallagher John","year":"2002"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90045-P"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_5"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2015.227"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/964001.964021"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44829-2_17"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46081-8_12"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5_14"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738002"},{"key":"e_1_2_2_25_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"12","author":"Madhusudan Parthasarathy","year":"2011"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_15"},{"key":"e_1_2_2_27_1","unstructured":"Jonathan May and Kevin Knight. 2008. A Primer on Tree Automata Software for Natural Language Processing. (2008).  Jonathan May and Kevin Knight. 2008. A Primer on Tree Automata Software for Natural Language Processing. (2008)."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48294-6_10"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738007"},{"key":"e_1_2_2_31_1","volume-title":"Neurosymbolic program synthesis. arXiv preprint arXiv:1611.01855","author":"Parisotto Emilio","year":"2016"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872387"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908093"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_2_2_35_1","volume-title":"Working Conference on Verified Software: Theories, Tools, and Experiments. Springer, 1\u201321","author":"R\u00fcmmer Philipp","year":"2013"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784757"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the 4th International Joint Conference on Artificial Intelligence (IJCAI). 260\u2013267","author":"Shaw David E."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2977797.2977807"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837668"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025153"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908102"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_2_44_1","first-page":"57","article-title":"Generalized finite automata theory with an application to a decision problem of second-order logic","volume":"2","author":"Thatcher James W","year":"1968","journal-title":"Theory of Computing Systems"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21401-6_33"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462174"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706338"},{"key":"e_1_2_2_48_1","volume-title":"Program Synthesis using Abstraction Refinement. arXiv preprint arXiv:1710.07740","author":"Wang Xinyu","year":"2017"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133886"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984030"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908088"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670518.2673879"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158151","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158151","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":50,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158151"],"URL":"https:\/\/doi.org\/10.1145\/3158151","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}