{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T09:58:05Z","timestamp":1776333485292,"version":"3.51.2"},"reference-count":44,"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\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery"],"award-info":[{"award-number":["Discovery"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ontario Ministry of Research","award":["Early Researcher Award"],"award-info":[{"award-number":["Early Researcher Award"]}]}],"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            Many problems in formal methods can be formalized as two-player games. For several applications\u2014program synthesis, for example\u2014in addition to determining which player wins the game, we are interested in computing a winning strategy for that player. This paper studies the strategy synthesis problem for games defined within the theory of linear rational arithmetic. Two types of games are considered. A\n            <jats:italic>satisfiability game<\/jats:italic>\n            , described by a quantified formula, is played by two players that take turns instantiating quantifiers. The objective of each player is to prove (or disprove) satisfiability of the formula. A\n            <jats:italic>reachability game<\/jats:italic>\n            , described by a pair of formulas defining the legal moves of each player, is played by two players that take turns choosing positions\u2014rational vectors of some fixed dimension. The objective of each player is to reach a position where the opposing player has no legal moves (or to play the game forever). We give a complete algorithm for synthesizing winning strategies for satisfiability games and a sound (but necessarily incomplete) algorithm for synthesizing winning strategies for reachability games.\n          <\/jats:p>","DOI":"10.1145\/3158149","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":27,"title":["Strategy synthesis for linear arithmetic games"],"prefix":"10.1145","volume":"2","author":[{"given":"Azadeh","family":"Farzan","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary","family":"Kincaid","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837628"},{"key":"e_1_2_2_2_1","volume-title":"Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa.","author":"Alur Rajeev","year":"2013"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_14"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.10"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535860"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958031.2958062"},{"key":"e_1_2_2_7_1","unstructured":"Nikolaj Bj\u00f8rner and Mikol\u00e1s Janota. 2015. Playing with Quantified Satisfaction. In LPAR - short presentations. 15\u201327.  Nikolaj Bj\u00f8rner and Mikol\u00e1s Janota. 2015. Playing with Quantified Satisfaction. In LPAR - short presentations. 15\u201327."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45221-5_13"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33475-7_5"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_60"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80534-6"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2491969"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2016.XII.002"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44685-0_36"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_2_16_1","unstructured":"Azadeh Farzan and Zachary Kincaid. 2016. Linear Arithmetic Satisfiability via Strategy Improvement. In IJCAI. 735\u2013743.  Azadeh Farzan and Zachary Kincaid. 2016. Linear Arithmetic Satisfiability via Strategy Improvement. In IJCAI. 735\u2013743."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11901914_25"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-011-0202-1"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204006"},{"key":"e_1_2_2_21_1","volume-title":"Infinite games with perfect information. Contributions to the Theory of Games 2","author":"Gale David","year":"1953"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Orna Grumberg Martin Lange Martin Leucker and Sharon Shoham. 2005. Don\u2019t know in the \u00b5-calculus. In VMCAI. 233\u2013249.  Orna Grumberg Martin Lange Martin Leucker and Sharon Shoham. 2005. Don\u2019t know in the \u00b5-calculus. In VMCAI. 233\u2013249.","DOI":"10.1007\/978-3-540-30579-8_16"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.10.009"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Ashutosh Gupta Thomas A. Henzinger Rupak Majumdar Andrey Rybalchenko and Ru-Gang Xu. 2008. Proving nontermination. In POPL. 147\u2013158.  Ashutosh Gupta Thomas A. Henzinger Rupak Majumdar Andrey Rybalchenko and Ru-Gang Xu. 2008. Proving nontermination. In POPL. 147\u2013158.","DOI":"10.1145\/1328897.1328459"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11691372_14"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31980-1_31"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093883627"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.4169\/math.mag.84.4.278"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_23"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806632"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48320-9_27"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/357084.357090"},{"key":"e_1_2_2_33_1","volume-title":"Introduction to model theory. Model theory, algebra, and geometry 39","author":"Marker David","year":"2000"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971035"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11817963_14"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Nir Piterman Amir Pnueli and Yaniv Sa\u00e2\u0102\u0179ar. 2006. Synthesis of reactive(1) designs. In VMCAI. 364\u2013380.  Nir Piterman Amir Pnueli and Yaniv Sa\u00e2\u0102\u0179ar. 2006. Synthesis of reactive(1) designs. In VMCAI. 364\u2013380.","DOI":"10.1007\/11609773_24"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Amir Pnueli and Yonit Kesten. 2002. A Deductive Proof System for CTL*. In CONCUR. 24\u201340.  Amir Pnueli and Yonit Kesten. 2002. A Deductive Proof System for CTL*. In CONCUR. 24\u201340.","DOI":"10.1007\/3-540-45694-5_2"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21668-3_12"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706337"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-012-0223-4"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59042-0_57"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706338"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2894"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158149","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158149","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\/3158149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":44,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158149"],"URL":"https:\/\/doi.org\/10.1145\/3158149","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"}}]}}