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
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

The Multiple Dimensions of Mean-Payoff Games

(Extended Abstract)

verfasst von : Laurent Doyen

Erschienen in: Reachability Problems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Outline We consider quantitative game models for the design of reactive systems working in resource-constrained environment. The game is played on a finite weighted graph where some resource (e.g., battery) can be consumed or recharged along the edges of the graph.

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 "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

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
Nächstes Kapitel Adding Dense-Timed Stack to Integer Reset Timed Automata
Literatur
1.
2.
Alur, R., Degorre, A., Maler, O., Weiss, G.: On omega-languages defined by mean-payoff conditions. In: Alfaro, L. (ed.) FoSSaCS 2009. LNCS, vol. 5504, pp. 333–347. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-00596-1_​24 CrossRef
3.
4.
Basset, N., Kwiatkowska, M., Topcu, U., Wiltsche, C.: Strategy synthesis for stochastic games with multiple long-run objectives. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 256–271. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46681-0_​22
5.
Bohy, A., Bruyère, V., Filiot, E., Raskin, J.-F.: Synthesis from LTL specifications with mean-payoff objectives. In: Piterman, N., Smolka, S.A. (eds.) TACAS 2013. LNCS, vol. 7795, pp. 169–184. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-36742-7_​12 CrossRef
6.
Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: Cassez, F., Jard, C. (eds.) FORMATS 2008. LNCS, vol. 5215, pp. 33–47. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-85778-5_​4 CrossRef
7.
Brázdil, T., Brožek, V., Chatterjee, K., Forejt, V., Kučera, A.: Markov decision processes with multiple long-run average objectives. Logical Meth. Comput. Sci.10(1:13) (2014)
8.
9.
Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.-F.: Faster algorithms for mean-payoff games. Formal Meth. Syst. Des. 38(2), 97–118 (2011)CrossRefMATH
10.
Büchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Trans. Am. Math. Soc. 138, 295–311 (1969)MathSciNetCrossRefMATH
11.
12.
13.
Chatterjee, K., Doyen, L.: Energy parity games. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 599–610. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14162-1_​50 CrossRef
14.
Chatterjee, K., Doyen, L.: Perfect-information stochastic games with generalized mean-payoff objectives. In: Proceedings of LICS: Logic in Computer Science, pp. 247–256. ACM (2016)
15.
Chatterjee, K., Doyen, L., Edelsbrunner, H., Henzinger, T.A., Rannou, P.: Mean-payoff automaton expressions. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 269–283. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15375-4_​19 CrossRef
16.
Chatterjee, K., Doyen, L., Gimbert, H., Oualhadj, Y.: Perfect-information stochastic mean-payoff parity games. In: Muscholl, A. (ed.) FoSSaCS 2014. LNCS, vol. 8412, pp. 210–225. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54830-7_​14 CrossRef
17.
Chatterjee, K., Doyen, L., Randour, M., Raskin, J.-F.: Looking at mean-payoff and total-payoff through windows. In: Hung, D., Ogawa, M. (eds.) ATVA 2013. LNCS, vol. 8172, pp. 118–132. Springer, Cham (2013). doi:10.​1007/​978-3-319-02444-8_​10 CrossRef
18.
Chatterjee, K., Henzinger, T.A.: A survey of stochastic \(\omega \)-regular games. J. Comput. Syst. Sci. 78(2), 394–413 (2012)MathSciNetCrossRefMATH
19.
Chatterjee, K., Henzinger, T.A., Jurdziński, M.: Mean-payoff parity games. In: Proceedings of LICS: Logic in Computer Science, pp. 178–187. IEEE Computer Society (2005)
20.
Chatterjee, K., Randour, M., Raskin, J.-F.: Strategy synthesis for multi-dimensional quantitative objectives. Acta Inf. 51, 129–163 (2014)MathSciNetCrossRefMATH
21.
Chatterjee, K., Velner, Y.: Hyperplane separation technique for multidimensional mean-payoff games. In: D’Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013. LNCS, vol. 8052, pp. 500–515. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40184-8_​35 CrossRef
22.
Degorre, A., Doyen, L., Gentilini, R., Raskin, J.-F., Toruńczyk, S.: Energy and mean-payoff games with imperfect information. In: Dawar, A., Veith, H. (eds.) CSL 2010. LNCS, vol. 6247, pp. 260–274. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15205-4_​22 CrossRef
23.
24.
Emerson, E.A., Jutla, C.: Tree automata, mu-calculus and determinacy. In: Proceedings of FOCS: Foundations of Computer Science, pp. 368–377. IEEE (1991)
25.
26.
27.
Gurevich, Y., Harrington, L.: Trees, automata, and games. In: Proceedings of STOC: Symposium on Theory of Computing, pp. 60–65. ACM Press (1982)
28.
Hunter, P., Pérez, G.A., Raskin, J.-F.: Mean-payoff games with partial-observation. In: Ouaknine, J., Potapov, I., Worrell, J. (eds.) RP 2014. LNCS, vol. 8762, pp. 163–175. Springer, Cham (2014). doi:10.​1007/​978-3-319-11439-2_​13
29.
Hunter, P., Raskin, J.-F.: Quantitative games with interval objectives. In: Proceedings of FSTTCS: Foundation of Software Technology and Theoretical Computer Science, vol. 29 of LIPIcs, pp. 365–377. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)
30.
31.
Jurdziński, M., Lazić, R., Schmitz, S.: Fixed-dimensional energy games are in pseudo-polynomial time. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 260–272. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47666-6_​21 CrossRef
32.
33.
Kelmendi, E.: Two-Player Stochastic Games with Perfect and Zero Information. Ph.D. thesis, Université de Bordeaux (2016)
34.
Kopczyński, E.: Half-positional determinacy of infinite games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 336–347. Springer, Heidelberg (2006). doi:10.​1007/​11787006_​29 CrossRef
35.
Pérez, G.A.: The fixed initial credit problem for partial-observation energy games is Ack-complete. Inform. Process. Lett. 118, 91–99 (2017)MathSciNetCrossRefMATH
36.
Pnueli, A., Rosner R.: On the synthesis of a reactive module. In: Proceedings of POPL, pp. 179–190. ACM Press (1989)
37.
Rabin, M.O.: Automata on Infinite Objects and Church’s Problem. American Mathematical Society, Boston (1972)CrossRefMATH
38.
Ramadge, P.J., Wonham, W.M.: The control of discrete event systems. Proc. IEEE 77, 81–98 (1989)CrossRefMATH
39.
Raskin, J.-F.: A tutorial on mean-payoff and energy games. Dependable Softw. Syst. Eng. 45, 179–201 (2016)
40.
Velner, Y.: Finite-memory strategy synthesis for robust multidimensional mean-payoff objectives. In Proceedings of CSL-LICS: Joint Meeting of Computer Science Logic (CSL) and Logic in Computer Science (LICS), pp. 79:1–79:10. ACM (2014)
41.
42.
Velner, Y., Chatterjee, K., Doyen, L., Henzinger, T.A., Rabinovich, A.M., Raskin, J.-F.: The complexity of multi-mean-payoff and multi-energy games. Inf. Comput. 241, 177–196 (2015)MathSciNetCrossRefMATH
43.
Metadaten
Titel
The Multiple Dimensions of Mean-Payoff Games
verfasst von
Laurent Doyen
Copyright-Jahr
2017
Buch
Reachability Problems

Print ISBN: 978-3-319-67088-1

Electronic ISBN: 978-3-319-67089-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-67089-8_1