{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:00Z","timestamp":1750309140752,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T00:00:00Z","timestamp":1713225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            In\n            <jats:italic>rational synthesis<\/jats:italic>\n            , we automatically construct a reactive system that satisfies its specification in all rational environments, namely environments that have objectives and act to fulfill them. We complete the study of the complexity of LTL rational synthesis, when the objectives are given by formulas in Linear Temporal Logic. Our contribution is threefold. First, we tighten the known upper bounds for settings that were left open in earlier work. Second, our complexity analysis is parametric, and we describe tight upper and lower bounds in each of the problem parameters: the game graph, the objectives of the system components, and the objectives of the environment components. Third, we generalize the definition of rational synthesis by adding hostile players to the setting and by combining the cooperative and non-cooperative approaches studied in earlier work.\n          <\/jats:p>","DOI":"10.1145\/3648473","type":"journal-article","created":{"date-parts":[[2024,2,28]],"date-time":"2024-02-28T12:51:21Z","timestamp":1709124681000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of LTL Rational Synthesis"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4699-6117","authenticated-orcid":false,"given":"Orna","family":"Kupferman","sequence":"first","affiliation":[{"name":"The Hebrew University, Jerusalem, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1994-6835","authenticated-orcid":false,"given":"Noam","family":"Shenwald","sequence":"additional","affiliation":[{"name":"The Hebrew University, Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2024,4,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304422"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585270"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.68"},{"key":"e_1_3_3_5_2","first-page":"1588","volume-title":"Proceedings of the 28th International Joint Conference on Artificial Intelligence","author":"Bouyer-Decitre Patricia","year":"2019","unstructured":"Patricia Bouyer-Decitre, Orna Kupferman, Nicolas Markey, Bastien Maubert, Aniello Murano, and Giuseppe Perelli. 2019. Reasoning about quality and fuzziness of strategic behaviours. In Proceedings of the 28th International Joint Conference on Artificial Intelligence. 1588\u20131594."},{"key":"e_1_3_3_6_2","volume-title":"Synthesis of Interactive Reactive Systems. (Synth\u00e8se des syst\u00e8mes r\u00e9actifs interactifs)","author":"Bozianu R.","year":"2016","unstructured":"R. Bozianu. 2016. Synthesis of Interactive Reactive Systems. (Synth\u00e8se des syst\u00e8mes r\u00e9actifs interactifs). Ph. D. Dissertation. University of Paris-Est, France."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85361-9_14"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2392200.2392207"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.07.004"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30124-0_6"},{"key":"e_1_3_3_12_2","first-page":"23","volume-title":"Proceedings of the International Congress of Mathematicians, 1962","author":"Church Alonzo","year":"1963","unstructured":"Alonzo Church. 1963. Logic, arithmetics, and automata. In Proceedings of the International Congress of Mathematicians, 1962. Institut Mittag-Leffler, 23\u201335."},{"key":"e_1_3_3_13_2","series-title":"LIPIcs","first-page":"121:1\u2013121:15","volume-title":"Proceedings of the 43th International Colloquium on Automata, Languages, and Programming","volume":"55","author":"Condurache Rodica","year":"2016","unstructured":"Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, and J.-F. Raskin. 2016. The complexity of rational synthesis. In Proceedings of the 43th International Colloquium on Automata, Languages, and Programming(LIPIcs, Vol. 55). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 121:1\u2013121:15."},{"key":"e_1_3_3_14_2","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"38:1\u201338:15","volume-title":"Proceedings of the 29th International Conference on Concurrency Theory","volume":"118","author":"Condurache Rodica","year":"2018","unstructured":"Rodica Condurache, Youssouf Oualhadj, and Nicolas Troquard. 2018. The complexity of rational synthesis for concurrent games. In Proceedings of the 29th International Conference on Concurrency Theory(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 118). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 38:1\u201338:15."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21949"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12002-2_16"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367080"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.023"},{"key":"e_1_3_3_19_2","first-page":"615","volume-title":"Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science","author":"Kupferman Orna","year":"2011","unstructured":"Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, and Mihalis Yannakakis. 2011. Temporal synthesis for bounded systems and environments. In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science. 615\u2013626."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-016-9508-8"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00596-1_14"},{"key":"e_1_3_3_22_2","series-title":"LIPIcs","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 Orna","year":"2020","unstructured":"Orna Kupferman and Noam Shenwald. 2020. Perspective games with notifications. In Proceedings of the 40th Conference on Foundations of Software Technology and Theoretical Computer Science(LIPIcs, Vol. 182). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 51:1\u201351:16."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470616"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785662"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.66"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380883"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90110-9"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75293"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90026-7"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.9878"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3648473","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3648473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:19Z","timestamp":1750287019000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3648473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,16]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3648473"],"URL":"https:\/\/doi.org\/10.1145\/3648473","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2024,4,16]]},"assertion":[{"value":"2023-05-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}