تقرير
Computing Adequately Permissive Assumptions for Synthesis
| العنوان: | Computing Adequately Permissive Assumptions for Synthesis |
|---|---|
| المؤلفون: | Anand, Ashwani, Mallik, Kaushik, Nayak, Satya Prakash, Schmuck, Anne-Kathrin |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory |
| الوصف: | We solve the problem of automatically computing a new class of environment assumptions in two-player turn-based finite graph games which characterize an ``adequate cooperation'' needed from the environment to allow the system player to win. Given an $\omega$-regular winning condition $\Phi$ for the system player, we compute an $\omega$-regular assumption $\Psi$ for the environment player, such that (i) every environment strategy compliant with $\Psi$ allows the system to fulfill $\Phi$ (sufficiency), (ii) $\Psi$ can be fulfilled by the environment for every strategy of the system (implementability), and (iii) $\Psi$ does not prevent any cooperative strategy choice (permissiveness). For parity games, which are canonical representations of $\omega$-regular games, we present a polynomial-time algorithm for the symbolic computation of adequately permissive assumptions and show that our algorithm runs faster and produces better assumptions than existing approaches -- both theoretically and empirically. To the best of our knowledge, for $\omega$-regular games, we provide the first algorithm to compute sufficient and implementable environment assumptions that are also permissive. Comment: TACAS 2023 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1007/978-3-031-30820-8_15 |
| URL الوصول: | http://arxiv.org/abs/2301.07563 |
| رقم الأكسشن: | edsarx.2301.07563 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1007/978-3-031-30820-8_15 |
|---|