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 8/2018

11.10.2017 | Original Article

Looking at mean payoff through foggy windows

verfasst von: Paul Hunter, Guillermo A. Pérez, Jean-François Raskin

Erschienen in: Acta Informatica | Ausgabe 8/2018

Einloggen

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

search-config
loading …

Abstract

Mean-payoff games (MPGs) are infinite duration two-player zero-sum games played on weighted graphs. Under the hypothesis of full observation, they admit memoryless optimal strategies for both players and can be solved in \({\mathsf {NP}}\cap {\mathsf {coNP}}\). MPGs are suitable quantitative models for open reactive systems. However, in this context the assumption of full observation is not always realistic. For the partial-observation case, the problem that asks if the first player has an observation-based winning strategy that enforces a given threshold on the mean payoff, is undecidable. In this paper, we study the window mean-payoff objectives introduced recently as an alternative to the classical mean-payoff objectives. We show that, in sharp contrast to the classical mean-payoff objectives, some of the window mean-payoff objectives are decidable in games with partial observation.
Vorheriger Artikel Preface for the special issue for ATVA 2015
Nächster Artikel TSO-to-TSO linearizability is undecidable

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
Fußnoten
1
The terms belief and knowledge are used to denote a state from any variation of the classic “Reif construction” [19] to turn a game with partial observation into a game with full observation. Other names for similar constructions include “knowledge-based subset construction” (see e.g. [10]).
 
2
We refer the reader who is not familiar with parity automata or games to [22].
 
Literatur
1.
Almagor, S., Boker, U., Kupferman, O.: What’s decidable about weighted automata? In: ATVA, pp. 482–491. Springer (2011)
2.
Berwanger, D., Chatterjee, K., De Wulf, M., Doyen, L., Henzinger, T.A.: Alpaga: a tool for solving parity games with imperfect information. In: TACAS, volume 5505 of LNCS. Springer (2009)
3.
Björklund, H., Sandberg, S., Vorobyov, S.: Memoryless determinacy of parity and mean payoff games: a simple proof. TCS 310(1), 365–378 (2004)MathSciNetCrossRef
4.
Bohy, A., Bruyère, V., Filiot, E., Jin, N., Raskin, J.F.: Acacia+, a tool for LTL synthesis. In: CAV, pp. 652–657. Springer (2012)
5.
Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.F.: Faster algorithms for mean-payoff games. FMSD 38(2), 97–118 (2011)MATH
6.
Chakrabarti, A., de Alfaro, L., Henzinger, T.A., Stoelinga, M.: Resource interfaces. In: EMSOFT, volume 2855 of LNCS. Springer (2003)
7.
Chatterjee, K., Doyen, L.: The complexity of partial-observation parity games. In: LPAR, pp. 1–14. Springer (2010)
8.
Chatterjee, K., Doyen, L., Henzinger, T.A, Raskin, J.F.: Algorithms for omega-regular games with imperfect information. In: CSL, pp. 287–302 (2006)CrossRef
9.
Chatterjee, K., Doyen, L., Randour, M., Raskin, J.F.: Looking at mean-payoff and total-payoff through windows. In: ATVA, pp. 118–132. Springer (2013)
10.
Degorre, A., Doyen, L., Gentilini, R., Raskin, J.F., Toruńczyk, S.: Energy and mean-payoff games with imperfect information. In: CSL, pp. 260–274 (2010)CrossRef
11.
12.
Doyen, L., Raskin, J.F.: Antichain algorithms for finite automata. In TACAS, volume 6015 of LNCS, pp. 2–22. Springer (2010)
13.
Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8, 109–113 (1979)MathSciNetCrossRef
14.
Allen Emerson, E., Jutla, Charanjit S.: Tree automata, mu-calculus and determinacy (extended abstract). In: STOCS, pp. 368–377. IEEE (1991)
15.
16.
Grädel, E.: Positional determinacy of infinite games. In: STACS, pp. 4–18. Springer (2004)
17.
Jurdziński, M.: Small progress measures for solving parity games. In: STACS, volume 1770 of LNCS, pp. 290–301. Springer (2000)
18.
19.
Reif, J.H.: The complexity of two-player games of incomplete information. J. Comput Syst. Sci. 29(2), 274–301 (1984)MathSciNetCrossRef
20.
Safra, S.: On the complexity of \(\omega \)-automata. In: FOCS, pp. 319–327. IEEE (1988)
21.
Safra, S.: Exponential determinization for omega-automata with strong-fairness acceptance condition (extended abstract). In: STOC, pp. 275–282 (1992)
22.
Thomas, W.: On the synthesis of strategies in infinite games. In: STACS, pp. 1–13. Springer (1995)
23.
Metadaten
Titel
Looking at mean payoff through foggy windows
verfasst von
Paul Hunter
Guillermo A. Pérez
Jean-François Raskin
Publikationsdatum
11.10.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
Acta Informatica / Ausgabe 8/2018
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-017-0304-7

Weitere Artikel der Ausgabe 8/2018

Acta Informatica 8/2018 Zur Ausgabe

Original Article

TSO-to-TSO linearizability is undecidable

Editorial

Preface for the special issue for ATVA 2015

Original Article

Spanning the spectrum from safety to liveness

Original Article

Hierarchical information and the synthesis of distributed strategies