{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:27Z","timestamp":1750309407680,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T00:00:00Z","timestamp":1705449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            We introduce and study\n            <jats:italic>perspective games<\/jats:italic>\n            , which model multi-agent systems in which agents can view only the parts of the system that they own. As in standard multi-player turn-based games, the vertices of the game graph are partitioned among the players. Starting from an initial vertex, the players jointly generate a computation, with each player deciding the successor vertex whenever the generated computation reaches a vertex she owns. A perspective strategy for a player depends only on the history of visits in her vertices. Thus, unlike observation-based models of partial visibility, where uncertainty is longitudinal\u2014players partially observe all vertices in the history, uncertainty in the perspective model is transverse\u2014players fully observe part of the vertices in the history.\n          <\/jats:p>\n          <jats:p>\n            We consider deterministic and probabilistic perspective games, with structural (e.g., B\u00fcchi or parity) and behavioral (e.g., LTL formulas) winning conditions. For these settings, we study the theoretical properties of the game as well as the decidability and complexity of the problem of deciding whether a player has a winning perspective strategy, in terms of both the game graph and the objectives. We compare perspective strategies with memoryless ones, and study an extension of the temporal logic ATL\n            <jats:sup>\u22c6<\/jats:sup>\n            with path quantifiers that capture perspective and memoryless strategies.\n          <\/jats:p>","DOI":"10.1145\/3627705","type":"journal-article","created":{"date-parts":[[2023,10,30]],"date-time":"2023-10-30T21:55:15Z","timestamp":1698702915000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Perspective Games"],"prefix":"10.1145","volume":"25","author":[{"given":"Orna","family":"Kupferman","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, The Hebrew University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gal","family":"Vardi","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, The Hebrew University, Israel,and TTI-Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,17]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6567024"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11229-005-3875-8"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/1661445.1661550"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01782772"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"e_1_3_2_7_2","first-page":"615","volume-title":"Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning","author":"Aminof B.","year":"2018","unstructured":"B. Aminof, G. De Giacomo, A. Murano, and S. Rubin. 2018. Synthesis under assumptions. In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning. 615\u2013616."},{"key":"e_1_3_2_8_2","first-page":"287","volume-title":"Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures","author":"Baier C.","year":"2008","unstructured":"C. Baier, N. Bertrand, and M. Gr\u00f6\u00dfer. 2008. On decision problems for probabilistic B\u00fcchi automata. In Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures. Springer, 287\u2013301."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/14"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005136"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.09.006"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-013-9231-3"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4_17"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055409"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.4"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16242-8_1"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15155-2_23"},{"issue":"3","key":"e_1_3_2_19_2","article-title":"Algorithms for omega-regular games with imperfect information","volume":"3","author":"Chatterjee K.","year":"2007","unstructured":"K. Chatterjee, L. Doyen, T. Henzinger, and J.-F. Raskin. 2007. Algorithms for omega-regular games with imperfect information. Logical Methods in Computer Science 3, 3 (2007).","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.07.004"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743507"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(87)90036-0"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209164"},{"key":"e_1_3_2_24_2","series-title":"Peroceedings of the 5th International Haifa Verification Conference,","first-page":"71","volume":"6405","author":"Fisman D.","year":"2009","unstructured":"D. Fisman and O. Kupferman. 2009. Reasoning about Finite-State Switched Systems. In Peroceedings of the 5th International Haifa Verification Conference,Lecture Notes in Computer Science, Vol. 6405. Springer, 71\u201386."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9294-4"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.023"},{"key":"e_1_3_2_28_2","first-page":"304","volume-title":"Proceedings of the 18th ACM Symposium on Theory of Computing","author":"Halpern J.Y.","year":"1986","unstructured":"J.Y. Halpern and M.Y. Vardi. 1986. The complexity of reasoning about knowledge and time: Extended abstract. In Proceedings of the 18th ACM Symposium on Theory of Computing. ACM, 304\u2013315."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90039-8"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/3237383.3237413"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2006.22"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_23"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9455-6"},{"key":"e_1_3_2_34_2","first-page":"51:1\u201351:16","volume-title":"Proceedings of the 40th Conference on Foundations of Software Technology and Theoretical Computer Science","volume":"182","author":"Kupferman O.","year":"2020","unstructured":"O. Kupferman and N. Shenwald. 2020. Perspective games with notifications. In Proceedings of the 40th Conference on Foundations of Software Technology and Theoretical Computer Science, Vol. 182. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 51:1\u201351:16."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470616"},{"issue":"4","key":"e_1_3_2_36_2","article-title":"Flow logic","volume":"15","author":"Kupferman O.","year":"2019","unstructured":"O. Kupferman and G. Vardi. 2019. Flow logic. Logical Methods in Computer Science 15, 4 (2019).","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785662"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9586-5_6"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24730-2_43"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.66"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0017-8"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/318593.318622"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-012-0236-z"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2006.06.020"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.2307\/1971035"},{"key":"e_1_3_2_46_2","volume-title":"Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning","author":"Maubert B.","year":"2018","unstructured":"B. Maubert and A. Murano. 2018. Reasoning about knowledge and strategies under hierarchical information. In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.25"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.23"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89597"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15155-2_52"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90034-5"},{"key":"e_1_3_2_52_2","volume-title":"Modular Synthesis of Reactive Systems","author":"Rosner R.","year":"1992","unstructured":"R. Rosner. 1992. Modular Synthesis of Reactive Systems. Ph.D. Dissertation. Weizmann Institute of Science, Israel. UMI Order Number: DP17517."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)82604-0"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3837"},{"key":"e_1_3_2_55_2","series-title":"Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science,","first-page":"1","volume":"900","author":"Thomas W.","year":"1995","unstructured":"W. Thomas. 1995. On the synthesis of strategies in infinite games. In Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science,Lecture Notes in Computer Science, Vol. 900. Springer, 1\u201313."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.12"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90026-7"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1092"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(79)90653-3"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028832"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627705","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:04Z","timestamp":1750294684000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,17]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3627705"],"URL":"https:\/\/doi.org\/10.1145\/3627705","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2024,1,17]]},"assertion":[{"value":"2023-01-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}