Document Open Access Logo

Assume-Admissible Synthesis

Authors Romain Brenguier, Jean-François Raskin, Ocan Sankur

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2015.100.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Romain Brenguier
Jean-François Raskin
Ocan Sankur

Cite As Get BibTex

Romain Brenguier, Jean-François Raskin, and Ocan Sankur. Assume-Admissible Synthesis. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 100-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CONCUR.2015.100

Abstract

In this paper, we introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. It is based on the notion of admissible strategies. We compare our novel rule with previous rules defined in the literature, and we show that contrary to the previous proposals, our rule define sets of solutions which are rectangular. This property leads to solutions which are robust and resilient. We provide algorithms with optimal complexity and also an abstraction framework.

Subject Classification

Keywords
  • Multi-player games
  • controller synthesis
  • admissibility

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Brandenburger Adam, Friedenberg Amanda, H Jerome, et al. Admissibility in games. Econometrica, 2008. Google Scholar
  2. Dietmar Berwanger. Admissibility in infinite games. In Proc. of STACS'07, volume 4393 of LNCS, pages 188-199. Springer, February 2007. Google Scholar
  3. Roderick Bloem, Rüdiger Ehlers, Swen Jacobs, and Robert Könighofer. How to handle assumptions in synthesis. In SYNT'14, volume 157 of EPTCS, pages 34-50, 2014. Google Scholar
  4. Romain Brenguier, Jean-François Raskin, and Mathieu Sassolas. The complexity of admissibility in omega-regular games. In CSL-LICS'14, 2014. ACM, 2014. Google Scholar
  5. Krishnendu Chatterjee, Laurent Doyen, Emmanuel Filiot, and Jean-François Raskin. Doomsday equilibria for omega-regular games. In VMCAI'14, volume 8318, pages 78-97. Springer, 2014. Google Scholar
  6. Krishnendu Chatterjee and Thomas A Henzinger. Assume-guarantee synthesis. In TACAS'07, volume 4424 of LNCS. Springer, 2007. Google Scholar
  7. Krishnendu Chatterjee, Thomas A. Henzinger, and Barbara Jobstmann. Environment assumptions for synthesis. In CONCUR 2008, volume 5201 of LNCS, pages 147-161. Springer, 2008. Google Scholar
  8. Krishnendu Chatterjee, Thomas A Henzinger, and Marcin Jurdziński. Games with secure equilibria. Theoretical Computer Science, 365(1):67-82, 2006. Google Scholar
  9. Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman. Strategy logic. Inf. Comput., 208(6):677-693, 2010. Google Scholar
  10. Edmund M. Clarke and E. Allen Emerson. Design and synthesis of synchronization skeletons using branching-time temporal logic. In Logics of Programs, volume 131 of LNCS, pages 52-71. Springer, 1981. Google Scholar
  11. Patrick Cousot and Radhia Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In POPL'77. ACM, 1977. Google Scholar
  12. Werner Damm and Bernd Finkbeiner. Automatic compositional synthesis of distributed systems. In FM 2014, volume 8442 of LNCS, pages 179-193. Springer, 2014. Google Scholar
  13. Luca de Alfaro, Patrice Godefroid, and Radha Jagadeesan. Three-valued abstractions of games: Uncertainty, but with precision. In LICS'04. IEEE, 2004. Google Scholar
  14. E Allen Emerson. Temporal and modal logic. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), 995:1072, 1990. Google Scholar
  15. Marco Faella. Admissible strategies in infinite games over graphs. In MFCS 2009, volume 5734 of Lecture Notes in Computer Science, pages 307-318. Springer, 2009. Google Scholar
  16. Dana Fisman, Orna Kupferman, and Yoad Lustig. Rational synthesis. In TACAS'10, volume 6015 of LNCS, pages 190-204. Springer, 2010. Google Scholar
  17. Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, Cambridge, MA, 1991. Translated into Chinesse by Renin University Press, Bejing: China. Google Scholar
  18. Thomas A. Henzinger, Rupak Majumdar, Freddy Y. C. Mang, and Jean-François Raskin. Abstract interpretation of game properties. In SAS, pages 220-239, 2000. Google Scholar
  19. Paul Hunter. Complexity and Infinite Games on Finite Graphs. PhD thesis, Computer Laboratory, University of Cambridge, 2007. Google Scholar
  20. O. Kupferman, G. Perelli, and M.Y. Vardi. Synthesis with rational environments. In Proc. 12th European Conference on Multi-Agent Systems, LNCS. Springer, 2014. Google Scholar
  21. Zohar Manna and Pierre Wolper. Synthesis of communicating processes from temporal logic specifications. In Logics of Programs, volume 131 of LNCS, pages 253-281. Springer, 1981. Google Scholar
  22. Fabio Mogavero, Aniello Murano, and Moshe Y. Vardi. Reasoning about strategies. In FSTTCS 2010, volume 8 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010. Google Scholar
  23. John Nash. Equilibrium points in n-person games. Proc. NAS, 1950. Google Scholar
  24. Amir Pnueli. The temporal logic of programs. In Foundations of Computer Science, 1977., 18th Annual Symposium on, pages 46-57. IEEE, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact