{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:40:09Z","timestamp":1750228809953,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,18]],"date-time":"2015-06-18T00:00:00Z","timestamp":1434585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Center for Information Technology Innovation, Academia Sinica, Taiwan, ROC"},{"name":"grant MOST 103-2221-E-002-150-MY3, Taiwan, ROC"},{"name":"Engineering and Physical Science Research Council (EPSRC), UK","award":["EP\/H046623\/1"],"award-info":[{"award-number":["EP\/H046623\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2015,6,18]]},"abstract":"<jats:p>\n            We propose an extension to\n            <jats:italic>ATL<\/jats:italic>\n            (\n            <jats:italic>alternating-time temporal logic<\/jats:italic>\n            ), called\n            <jats:italic>BSIL<\/jats:italic>\n            (\n            <jats:italic>basic strategy-interaction logic<\/jats:italic>\n            ), for specifying collaboration among agents in a multiagent system. We show that BSIL is strictly more expressive than ATL\n            <jats:sup>+<\/jats:sup>\n            but incomparable with ATL\n            <jats:sup>*<\/jats:sup>\n            ,\n            <jats:italic>GL<\/jats:italic>\n            (\n            <jats:italic>game logic<\/jats:italic>\n            ), and\n            <jats:italic>AMC<\/jats:italic>\n            (\n            <jats:italic>alternating \u03bc-calculus<\/jats:italic>\n            ) in expressiveness. We show that a memoryful strategy is necessary for fulfilling a specification in BSIL. We establish that the BSIL model-checking problem is PSPACE-complete. However, BSIL model checking can be performed in time quadratic in the model for fixed formulas. The BSIL (and hence ATL\n            <jats:sup>+<\/jats:sup>\n            ) satisfiability is 2EXPTIME-complete. Finally, we report our experiment with a model checker for BSIL.\n          <\/jats:p>","DOI":"10.1145\/2734117","type":"journal-article","created":{"date-parts":[[2015,6,18]],"date-time":"2015-06-18T18:14:05Z","timestamp":1434651245000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["An Extension of ATL with Strategy Interaction"],"prefix":"10.1145","volume":"37","author":[{"given":"Farn","family":"Wang","sequence":"first","affiliation":[{"name":"Graduate Institute of Electronic Engineering, National Taiwan University; Department of Electrical Engineering, National Taiwan University; Research Center for Information Technology Innovation (CITI), Academia Sinica, Taiwan, ROC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Schewe","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, University of Liverpool, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chung-Hao","family":"Huang","sequence":"additional","affiliation":[{"name":"Graduate Institute of Electronic Engineering, National Taiwan University, Taipei, Taiwan, ROC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2007.45"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01257083"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92687-0_7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.07.004"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/5397.5399"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201910)","volume":"8","author":"Costa Arnaud Da","year":"2010","unstructured":"Arnaud Da Costa, Fran\u00e7ois Laroussinie, and Nicolas Markey. 2010. ATL with strategy contexts: Expressiveness and model checking. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201910) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 8. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 120--132."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682526"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90001-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/4904.4999"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(87)90036-0"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90039-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/938135.938145"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/646735.701643"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2893"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/567446.567463"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.119.18"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32940-1_15"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.32"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09764-0_10"},{"key":"e_1_2_1_22_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201910)","volume":"8","author":"Mogavero Fabio","unstructured":"Fabio Mogavero, Aniello Murano, and Moshe Y. Vardi. 2010. Reasoning about strategies. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201910) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 8. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 133--144."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00214-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1779046.1779067"},{"key":"e_1_2_1_25_1","article-title":"From nondeterministic B\u00fcchi and Streett automata to deterministic parity automata","volume":"3","author":"Piterman Nir","year":"2007","unstructured":"Nir Piterman. 2007. From nondeterministic B\u00fcchi and Streett automata to deterministic parity automata. Journal of Logical Methods in Computer Science 3, 3 (2007).","journal-title":"Journal of Logical Methods in Computer Science"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21948"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3266641.3266663"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004590"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3837"},{"key":"e_1_2_1_30_1","unstructured":"Lawrence J. Stockmeyer. 1974. The complexity of decision problems in automata theory and logic. MIT."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-003-0135-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2008.53"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88387-6_24"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.019"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-014-0312-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/646837.708476"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/938135.938146"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2734117","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2734117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:17:02Z","timestamp":1750227422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2734117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,18]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6,18]]}},"alternative-id":["10.1145\/2734117"],"URL":"https:\/\/doi.org\/10.1145\/2734117","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2015,6,18]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}