Optimal strategy synthesis for request-response games
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 179-203.

We show the existence and effective computability of optimal (even finite-state) winning strategies for request-response games in case the quality of a play is measured by the limit superior of the mean accumulated waiting times between requests and their responses.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2015005
Classification : 68Q45
Mots clés : Request-response games, optimal strategies, mean-payoff games
Horn, Florian 1 ; Thomas, Wolfgang 2 ; Wallmeier, Nico 2 ; Zimmermann, Martin 3

1 LIAFA, Université Denis Diderot - Paris 7, 75205 Paris cedex 13, France.
2 Lehrstuhl für Informatik 7, RWTH Aachen University, 52056 Aachen, Germany.
3 Reactive Systems Group, Saarland University, 66123 Saarbrücken, Germany.
@article{ITA_2015__49_3_179_0,
     author = {Horn, Florian and Thomas, Wolfgang and Wallmeier, Nico and Zimmermann, Martin},
     title = {Optimal strategy synthesis for request-response games},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {179--203},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {3},
     year = {2015},
     doi = {10.1051/ita/2015005},
     mrnumber = {3434598},
     zbl = {1347.68206},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2015005/}
}
TY  - JOUR
AU  - Horn, Florian
AU  - Thomas, Wolfgang
AU  - Wallmeier, Nico
AU  - Zimmermann, Martin
TI  - Optimal strategy synthesis for request-response games
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2015
SP  - 179
EP  - 203
VL  - 49
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2015005/
DO  - 10.1051/ita/2015005
LA  - en
ID  - ITA_2015__49_3_179_0
ER  - 
%0 Journal Article
%A Horn, Florian
%A Thomas, Wolfgang
%A Wallmeier, Nico
%A Zimmermann, Martin
%T Optimal strategy synthesis for request-response games
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2015
%P 179-203
%V 49
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2015005/
%R 10.1051/ita/2015005
%G en
%F ITA_2015__49_3_179_0
Horn, Florian; Thomas, Wolfgang; Wallmeier, Nico; Zimmermann, Martin. Optimal strategy synthesis for request-response games. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 179-203. doi : 10.1051/ita/2015005. http://archive.numdam.org/articles/10.1051/ita/2015005/

R. Alur, K. Etessami, S. La Torre and D. Peled, Parametric temporal logic for “model measuring”. ACM Trans. Comput. Log. 2 (2001) 388–407. | DOI | MR | Zbl

R. Bloem, K. Chatterjee, Th.A. Henzinger and B. Jobstmann, Better quality in synthesis through quantitative objectives. In CAV, vol. 5643 of Lect. Notes Comput. Sci. Edited by A. Bouajjani and O. Maler. Springer (2009) 140–156. | Zbl

T. Brázdil, K. Chatterjee, A. Kucera and P. Novotný, Efficient controller synthesis for consumption games with multiple resource types. In CAV, vol. 7358 of Lect. Notes Comput. Sci. Edited by P. Madhusudan and S.A. Seshia. Springer (2012) 23–38. | MR

P. Cerný, K. Chatterjee, Th.A. Henzinger, A. Radhakrishna and R. Singh, Quantitative synthesis for concurrent programs. In CAV, vol. 6806 of Lect. Notes Comput. Sci. Edited by G. Gopalakrishnan and S. Qadeer. Springer (2011) 243–259. | MR

K. Chatterjee and L. Doyen, Energy parity games. In ICALP 2, vol. 6199 of Lect. Notes Comput. Sci. Edited by S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide and P.G. Spirakis. Springer (2010) 599–610. | Zbl

K. Chatterjee, Th.A. Henzinger and M. Jurdziński, Mean-payoff parity games. In LICS. IEEE Computer Society (2005) 178–187.

K. Chatterjee, Th.A. Henzinger, and F. Horn, Finitary winning in ω-regular games. ACM Trans. Comput. Log. 11 (2009). | DOI | MR | Zbl

K. Chatterjee, Th.A. Henzinger and F. Horn, The complexity of request-response games. In LATA, vol. 6638 of Lect. Notes Comput. Sci. Edited by A.H. Dediu, Sh. Inenaga and C. Martín-Vide. Springer (2011) 227–237.

W. Czerwiński, T. Gogacz and E. Kopczyński, Lower bound for Dickson’s lemma in a special case. Found. Inform. 140 (2015) 123–127.

L.E. Dickson, Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Amer. J. Math. 35 (1913) 413–422. | DOI | JFM | MR

A. Ehrenfeucht and J. Mycielski, Positional strategies for mean payoff games. Int. J. Game Theory 8 (1979) 109–113. | DOI | MR | Zbl

U. Fahrenberg, L. Juhl, K.G. Larsen and J. Srba, Energy games in multiweighted automata. In ICTAC, vol. 6916 of Lect. Notes Comput. Sci. Edited by A. Cerone and P. Pihlajasaari. Springer (2011) 95–115. | MR

P. Faymonville and M. Zimmermann, Parametric linear dynamic logic. In GandALF, vol. 161 of EPTCS, 2014. Edited by A. Peron and C. Piazza. Preprint arXiv:1504.03880. | MR

N. Fijalkow and M. Zimmermann, Cost-parity and cost-Streett games. In FSTTCS 2012, vol. 18 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Edited by D. D’Souza, T. Kavitha and J. Radhakrishnan. Dagstuhl, Germany (2012) 124–135. | MR

F. Horn, W. Thomas and N. Wallmeier, Optimal strategy synthesis in request-response games. In ATVA, vol. 5311 of Lect. Notes Comput. Sci. Edited by S.D. Cha, J.-Y. Choi, M. Kim, I. Lee and M. Viswanathan. Springer (2008) 361–373. | Zbl

O. Kupferman, N. Piterman and M.Y. Vardi, From liveness to promptness. Formal Methods in System Design 34 (2009) 83–103. | DOI | Zbl

N. Wallmeier, Strategien in unendlichen Spielen mit Liveness-Gewinnbedingungen: Syntheseverfahren, Optimierung und Implementierung. Ph.D. thesis, RWTH Aachen University (2008).

N. Wallmeier, P. Hütten and W. Thomas, Symbolic synthesis of finite-state controllers for request-response specifications. In CIAA. Vol. 2759 of Lect. Notes Comput. Sci. Edited by O.H. Ibarra and Z. Dang. Springer (2003) 11–22. | MR | Zbl

M. Zimmermann, Time-optimal winning strategies for poset games. In CIAA, vol. 5642 of Lect. Notes Comput. Sci. Edited by S. Maneth. Springer (2009) 217–226. | MR | Zbl

M. Zimmermann, Optimal bounds in parametric LTL games. Theor. Comput. Sci. 493 (2013) 30–45. | DOI | MR | Zbl

M. Zimmermann, Parameterized linear temporal logics meet costs: Still not costlier than LTL (2015). Preprint arXiv:1505.06953. Accepted for publication at GandALF 2015. | MR

U. Zwick and M. Paterson, The complexity of mean payoff games on graphs. Theoret. Comput. Sci. 158 (1996) 343–359. | DOI | MR | Zbl

Cité par Sources :