2026-07-28T22:52:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20800 2024-08-29T05:40:58Z ddc:004 open_access

Faster and Smaller Solutions of Obliging Games Hausmann, Daniel Piterman, Nir Two-player games reactive synthesis Emerson-Lei games parity games Obliging games have been introduced in the context of the game perspective on reactive synthesis in order to enforce a degree of cooperation between the to-be-synthesized system and the environment. Previous approaches to the analysis of obliging games have been small-step in the sense that they have been based on a reduction to standard (non-obliging) games in which single moves correspond to single moves in the original (obliging) game. Here, we propose a novel, large-step view on obliging games, reducing them to standard games in which single moves encode long-term behaviors in the original game. This not only allows us to give a meaningful definition of the environment winning in obliging games, but also leads to significantly improved bounds on both strategy sizes and the solution runtime for obliging games. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Hausmann and Nir Piterman 2024 Is Part Of LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2024.28 urn:nbn:de:0030-drops-208008 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode