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.
Accepté le :
DOI : 10.1051/ita/2015005
Mots-clés : Request-response games, optimal strategies, mean-payoff games
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita/2015005/
, , 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.
, , and , 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.
, and , Lower bound for Dickson’s lemma in a special case. Found. Inform. 140 (2015) 123–127.
, Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Amer. J. Math. 35 (1913) 413–422. | DOI | JFM | MR
and , 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
, and , 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
, 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
and , The complexity of mean payoff games on graphs. Theoret. Comput. Sci. 158 (1996) 343–359. | DOI | MR | Zbl
Cité par Sources :
