Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Acta Informatica
Erschienen in: Acta Informatica 1/2017

13.07.2016 | Original Article

Assume-admissible synthesis

verfasst von: Romain Brenguier, Jean-François Raskin, Ocan Sankur

Erschienen in: Acta Informatica | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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. This rule is based on the notion of admissible strategies. We compare this rule with previous rules defined in the literature, and show that contrary to the previous proposals, it defines sets of solutions which are rectangular. This property leads to solutions which are robust and resilient, and allows one to synthesize strategies separately for each agent. We provide algorithms with optimal complexity and also an abstraction framework compatible with the new rule.
Vorheriger Artikel Reactive synthesis without regret
Nächster Artikel Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
This rule was introduced in [11], under the name Doomsday equilibria, as a generalization of the AG rule of [7] to the case of n-players.
 
Literatur
1.
Bernet, J., Janin, D., Walukiewicz, I.: Permissive strategies: from parity games to safety games. RAIRO Theor. Inf. Appl. 36(3), 261–275 (2002)MathSciNetCrossRefMATH
2.
Berwanger, D.: Admissibility in infinite games. In: Proceedings of STACS’07, vol. 4393 of LNCS, pp. 188–199. Springer, Berlin (2007)
3.
Bloem, R., Ehlers, R., Jacobs, S., Könighofer, R.: How to handle assumptions in synthesis. In: SYNT’14, vol. 157 of EPTCS, pp. 34–50 (2014)
4.
5.
Brenguier, R., Raskin, J.-F., Sassolas, M.: The complexity of admissibility in omega-regular games. In: CSL-LICS ’14, 2014. ACM (2014)
6.
Brenguier, R., Raskin, J.-F., Sankur, O.: Assume-admissible synthesis. In: Aceto L., de Frutos Escrig, D. (eds). 26th International Conference on Concurrency Theory (CONCUR 2015), vol. 42 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 100–113, Dagstuhl, Germany, 2015. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
7.
Chatterjee, K., Henzinger, T.A.: Assume-guarantee synthesis. In: TACAS’07, vol. 4424 of LNCS. Springer, Berlin (2007)
8.
Chatterjee, K., Henzinger, T.A., Jobstmann, B.: Environment assumptions for synthesis. In: CONCUR 2008, vol. 5201 of LNCS, pp. 147–161. Springer, Berlin (2008)
9.
10.
11.
Chatterjee, K., Doyen, L., Filiot, E., Raskin, J.-F.: Doomsday equilibria for omega-regular games. In: VMCAI’14, vol. 8318, pp. 78–97. Springer, Berlin (2014)
12.
Clarke, E.M., Emerson, E.A.: Design and synthesis of synchronization skeletons using branching-time temporal logic. In: Logics of Programs, vol. 131 of LNCS, pp. 52–71. Springer, Berlin (1981)
13.
Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL’77. ACM (1977)
14.
Damm, W., Finkbeiner, B.: Automatic compositional synthesis of distributed systems. In: FM 2014, vol. 8442 of LNCS, pp. 179–193. Springer, Berlin (2014)
15.
de Alfaro, L., Godefroid, P., Jagadeesan, R.: Three-valued abstractions of games: Uncertainty, but with precision. In: LICS’04. IEEE (2004)
16.
Emerson, E.A.: Temporal and modal logic. Handb. Theor. Comput. Sci. Vol. B Formal Models Semat B 995, 1072 (1990)
17.
Faella, M.: Admissible strategies in infinite games over graphs. In: MFCS 2009, vol. 5734 of Lecture Notes in Computer Science. pp. 307–318. Springer, Berlin (2009)
18.
Fisman, D., Kupferman, O., Lustig, Y.: Rational synthesis. In: TACAS’10, vol. 6015 of LNCS, pp. 190–204. Springer, Berlin (2010)
19.
Fudenberg, D., Tirole, J.: Game: Theory. MIT, Press, Cambridge, 1991 Translated into Chinesse by Renin University Press, Bejing (1991)
20.
Han, Z.: Game Theory in Wireless and Communication Networks: Theory, Models, and Applications. Cambridge University Press, UK (2012)MATH
21.
Henzinger, T.A., Majumdar, R., Mang, F.Y.C., Raskin, J.-F.: Abstract interpretation of game properties. In: SAS, pp. 220–239 (2000)
22.
Hunter, P.: Complexity and Infinite Games on Finite Graphs. Ph.D thesis, Computer Laboratory, University of Cambridge (2007)
23.
Hunter, P., Dawar, A.: Complexity bounds for regular games. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS’05, vol. 3618 of LNCS. Springer, Berlin (2005)
24.
Kupferman, O., Perelli, G., Vardi, M.Y.: Synthesis with rational environments. In: Proceedings of 12th European conference on multi-agent systems, LNCS. Springer, Berlin (2014)
25.
Long, D.E., Browne, A., Clarke, E.M., Jha, S., Marrero, W.R.: An improved algorithm for the evaluation of fixpoint expressions. In: CAV’94, vol. 818 of LNCS. Springer, Berlin (1994)
26.
Manna, Z., Wolper, P.: Synthesis of communicating processes from temporal logic specifications. In: Logics of Programs, vol. 131 of LNCS, pp. 253–281. Springer, Berlin (1981)
27.
Mogavero, F., Murano, A., Vardi, M.Y.: Reasoning about strategies. In: FSTTCS 2010, vol. 8 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)
28.
Nash, J.: Equilibrium points in \(n\)-person games. In: Proceedings of NAS (1950)
29.
Neider, D., Rabinovich, R., Zimmermann, M.: Down the borel hierarchy: solving muller games via safety games. Theor. Comput. Sci. 560, 219–234 (2014)MathSciNetCrossRefMATH
30.
Pnueli, A.: The temporal logic of programs. In: Foundations of Computer Science, 1977, 18th Annual Symposium on, pp. 46–57. IEEE (1977)
31.
32.
Ummels, M.: Stochastic Multiplayer Games: Theory and Algorithms. Amsterdam University Press, UK (2010)CrossRef
Metadaten
Titel
Assume-admissible synthesis
verfasst von
Romain Brenguier
Jean-François Raskin
Ocan Sankur
Publikationsdatum
13.07.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Acta Informatica / Ausgabe 1/2017
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-016-0273-2