{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:53:51Z","timestamp":1787500431730,"version":"build-2736575974"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1846122"],"award-info":[{"award-number":["1846122"]}],"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,1,7]]},"abstract":"<jats:p>\n                    Logic programming, as exemplified by datalog, defines the meaning of a program as its unique smallest model: the deductive closure of its inference rules. However, many problems call for an enumeration of models that vary along some set of choices while maintaining structural and logical constraints\u2014there is no single canonical model. The notion of\n                    <jats:italic toggle=\"yes\">stable models<\/jats:italic>\n                    for logic programs with negation has successfully captured programmer intuition about the set of valid solutions for such problems, giving rise to a family of programming languages and associated solvers known as answer set programming. Unfortunately, the definition of a stable model is frustratingly indirect, especially in the presence of rules containing free variables.\n                  <\/jats:p>\n                  <jats:p>\n                    We propose a new formalism,\n                    <jats:italic toggle=\"yes\">finite-choice logic programming,<\/jats:italic>\n                    that uses choice, not negation, to admit multiple solutions. Finite-choice logic programming contains all the expressive power of the stable model semantics, gives meaning to a new and useful class of programs, and enjoys a least-fixed-point interpretation over a novel domain. We present an algorithm for exploring the solution space and prove it correct with respect to our semantics. Our implementation, the Dusa logic programming language, has performance that compares favorably with state-of-the-art answer set solvers and exhibits more predictable scaling with problem size.\n                  <\/jats:p>","DOI":"10.1145\/3704849","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:48:42Z","timestamp":1736401722000},"page":"362-390","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Finite-Choice Logic Programming"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7026-0348","authenticated-orcid":false,"given":"Chris","family":"Martens","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2420-3067","authenticated-orcid":false,"given":"Robert J.","family":"Simmons","sequence":"additional","affiliation":[{"name":"Unaffiliated, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-0417-5636","authenticated-orcid":false,"given":"Michael","family":"Arntzenius","sequence":"additional","affiliation":[{"name":"Unaffiliated, Hamilton Township, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,9]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_16"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1988042.1988046"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-3384-5_11"},{"key":"e_1_3_2_6_1","first-page":"56","article-title":"Domain-Specific Heuristics in Answer Set Programming: A Declarative Non-Monotonic Approach","volume":"76","author":"Comploi-Taupe Richard","year":"2023","unstructured":"Richard Comploi-Taupe, Gerhard Friedrich, Konstantin Schekotihin, and Antonius Weinzierl. 2023. Domain-Specific Heuristics in Answer Set Programming: A Declarative Non-Monotonic Approach. J. Artif. Int. Res. 76 (may 2023), 56 pages. https:\/\/doi.org\/10.1613\/jair.1.14091 10.1613\/jair.1.14091","journal-title":"J. Artif. Int. Res."},{"key":"e_1_3_2_7_1","first-page":"228","volume-title":"Proceedings of the Sixth International Conference on Computational Creativity (ICCC 2015)","author":"Compton Kate","year":"2015","unstructured":"Kate Compton and Michael Mateas. 2015. Casual Creators. In Proceedings of the Sixth International Conference on Computational Creativity (ICCC 2015), Hannu Toivonen, Simon Colton, Michael Cook, and Dan Ventura (Eds.). Brigham Young University, Park City, Utah, 228\u2013235. http:\/\/computationalcreativity.net\/iccc2015\/proceedings\/10_2Compton.pdf"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28630-1_17"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36208-8_2"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1609\/aiide.v16i1.7406"},{"key":"e_1_3_2_12_1","unstructured":"Chinmaya Dabral Emma Tosch and Chris Martens. 2023. Exploring Consequences of Privacy Policies with Narrative Generation via Answer Set Programming. (2023). arXiv:2212.06719 Presented at Workshop on Programming Languages and the Law (ProLaLa@POPL)."},{"key":"e_1_3_2_13_1","doi-asserted-by":"crossref","unstructured":"Alessandro Dal Pal\u00f9 Agostino Dovier Enrico Pontelli and Gianfranco Rossi. 2009. GASP: Answer Set Programming with Lazy Grounding. Fundam. Inf. 96 3 (2009) 297\u2013322.","DOI":"10.3233\/FI-2009-180"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2011.2149523"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00588"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220611"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-31476-6_7"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90014-G"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90031-B"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000054"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1971622.1971623"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.001"},{"key":"e_1_3_2_24_1","first-page":"1070","volume-title":"Proceedings of International Logic Programming Conference and Symposium","author":"Gelfond Michael","year":"1988","unstructured":"Michael Gelfond and Vladimir Lifschitz. 1988. The Stable Model Semantics for Logic Programming. In Proceedings of International Logic Programming Conference and Symposium, Robert Kowalski and Kenneth A. Bowen (Eds.). MIT Press, 1070\u20131080."},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1699"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3607842"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563291"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068401001090"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1609\/aiide.v14i1.13026"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-89051-3_10"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v37i3.2672"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10003-2_82"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90007-P"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.12.071"},{"key":"e_1_3_2_35_1","doi-asserted-by":"crossref","unstructured":"Ravi Krishnamurthy and Shamim Naqvi. 1988. Non-Deterministic Choice in Datalog. In Proceedings of the Third International Conference on Data and Knowledge Bases C. Beeri J.W. Schmidt and U. Dayal (Eds.). Morgan Kaufmann 416\u2013424. https:\/\/doi.org\/10.1016\/B978-1-4832-1313-2.50038-X 10.1016\/B978-1-4832-1313-2.50038-X","DOI":"10.1016\/B978-1-4832-1313-2.50038-X"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158133"},{"key":"e_1_3_2_37_1","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1109\/VLHCC.2011.6070391","volume-title":"2011 IEEE Symposium on Visual Languages and Human-Centric Computing (VL\/HCC 2011)","author":"Le Duc","year":"2011","unstructured":"Duc Le, Eric Walkingshaw, and Martin Erwig. 2011. #ifdef confirmed harmful: Promoting understandable software variation. In 2011 IEEE Symposium on Visual Languages and Human-Centric Computing (VL\/HCC 2011). IEEE Computer Society, Los Alamitos, CA, USA, 143\u2013150. https:\/\/doi.org\/10.1109\/VLHCC.2011.6070391 10.1109\/VLHCC.2011.6070391"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2630"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414080.3414096"},{"key":"e_1_3_2_40_1","unstructured":"How Khang Lim Avishkar Mahajar Martin Strecker and Meng Weng Wong. 2022. Automating defeasible reasoning in law with answer set programming. CEUR 3193 (2022)."},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428193"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/581771.581774"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90068-W"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEEC.2015.7332726"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89982-2_15"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523707"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205035"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037171"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137852"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298572"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012801"},{"key":"e_1_3_2_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46669-8_33"},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42716-4"},{"key":"e_1_3_2_54_1","doi-asserted-by":"crossref","unstructured":"Tanya Short and Tarn Adams. 2017. Procedural generation in game design. CRC Press.","DOI":"10.1201\/9781315156378"},{"key":"e_1_3_2_55_1","unstructured":"Robert Simmons. 2024. Dusa implementation examples and benchmarking. Zenodo. https:\/\/doi.org\/10.5281\/zenodo.13983457 10.5281\/zenodo.13983457"},{"key":"e_1_3_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_28"},{"key":"e_1_3_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"e_1_3_2_58_1","article-title":"A logical approach to building dungeons: Answer set programming for hierarchical procedural content generation in roguelike games","author":"Smith Anthony J","year":"2014","unstructured":"Anthony J Smith and Joanna J Bryson. 2014. A logical approach to building dungeons: Answer set programming for hierarchical procedural content generation in roguelike games. In Proceedings of the 50th Anniversary Convention of the AISB.","journal-title":"Proceedings of the 50th Anniversary Convention of the AISB"},{"key":"e_1_3_2_59_1","first-page":"221","article-title":"Quantifying over play: Constraining undesirable solutions in puzzle design","author":"Smith Adam M","year":"2013","unstructured":"Adam M Smith, Eric Butler, and Zoran Popovic. 2013. Quantifying over play: Constraining undesirable solutions in puzzle design. In Foundations of Digital Games. 221\u2013228.","journal-title":"Foundations of Digital Games"},{"key":"e_1_3_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2011.2158545"},{"key":"e_1_3_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-07854-1_226"},{"key":"e_1_3_2_62_1","doi-asserted-by":"crossref","unstructured":"Leon S. Sterling. 1995. A Statistical Learning Method for Logic Programs with Distribution Semantics. MIT Press 715\u2013729. https:\/\/doi.org\/10.7551\/mitpress\/4298.003.0069 10.7551\/mitpress\/4298.003.0069","DOI":"10.7551\/mitpress\/4298.003.0069"},{"key":"e_1_3_2_63_1","doi-asserted-by":"publisher","DOI":"10.1609\/aiide.v14i1.13013"},{"key":"e_1_3_2_64_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.285"},{"key":"e_1_3_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116838"},{"key":"e_1_3_2_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-61660-5_17"},{"key":"e_1_3_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591239"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704849","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3704849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T10:15:13Z","timestamp":1770200113000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,7]]},"references-count":66,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2025,1,7]]}},"alternative-id":["10.1145\/3704849"],"URL":"https:\/\/doi.org\/10.1145\/3704849","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,7]]},"assertion":[{"value":"2024-07-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}