Games Where You Can Play Optimally with Arena-Independent Finite Memory

Bouyer, Patricia; Le Roux, Stéphane; Oualhadj, Youssouf; Randour, Mickaël; Vandenhove, Pierre

doi:10.4230/LIPIcs.CONCUR.2020.24

Download

Paper published in a journal (Scientific congresses and symposiums)

Games Where You Can Play Optimally with Arena-Independent Finite Memory

Bouyer, Patricia; Le Roux, Stéphane; Oualhadj, Youssouf et al.

2020 • In Leibniz International Proceedings in Informatics, 171, p. 24:1-24:22

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/20.500.12907/26884

DOI
10.4230/LIPIcs.CONCUR.2020.24

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

2001.03894.pdf

Author preprint (546.53 kB)

Download

All documents in ORBi UMONS are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Research center :

CREMMI - Modélisation mathématique et informatique

Disciplines :

Mathematics
Computer science

Author, co-author :

Bouyer, Patricia; Université Paris-Saclay > Laboratoire Méthodes Formelles (LMF)

Le Roux, Stéphane; Université Paris-Saclay > Laboratoire Méthodes Formelles (LMF)

Oualhadj, Youssouf; Univ Paris Est Creteil > LACL

Randour, Mickaël ; Université de Mons > Faculté des Sciences > Service de Mathématiques effectives

Vandenhove, Pierre ; Université de Mons - UMONS > Faculté des Sciences > Service de Mathématiques effectives ; Université Paris-Saclay > Laboratoire Méthodes Formelles (LMF)

Language :

English

Title :

Games Where You Can Play Optimally with Arena-Independent Finite Memory

Publication date :

01 September 2020

Event name :

International Conference on Concurrency Theory

Event place :

Vienna, Austria

Event date :

2020

Audience :

International

Journal title :

Leibniz International Proceedings in Informatics

ISSN :

1868-8969

Publisher :

[Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH], Germany

Volume :

171

Pages :

24:1-24:22

Peer review/Selection committee :

Peer Reviewed verified by ORBi

Research unit :

S820 - Mathématiques effectives

Research institute :

R150 - Institut de Recherche sur les Systèmes Complexes

Name of the research project :

4743 - ASP-Vandenhove - FrontieRS - Fédération Wallonie Bruxelles
3284 - CQ-Randour - ManySynth - Fédération Wallonie Bruxelles
3944 - MIS-Randour - ManySynth - Fédération Wallonie Bruxelles
3750 - MS FNRS IN-Oualhadj - Synthèse de contrôleurs pour systèmes réactifs: synthèse quantitative dans des environnements stochastiques - Fédération Wallonie Bruxelles

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Available on ORBi UMONS :

since 01 October 2020

Statistics

Number of views

49 (0 by UMONS)

Number of downloads

28 (0 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Benjamin Aminof and Sasha Rubin. First-cycle games. Inf. Comput., 254:195-216, 2017. doi:10.1016/j.ic.2016.10.008.
Roderick Bloem, Krishnendu Chatterjee, and Barbara Jobstmann. Graph games and reactive synthesis. In Edmund M. Clarke, Thomas A. Henzinger, Helmut Veith, and Roderick Bloem, editors, Handbook of Model Checking, pages 921-962. Springer, 2018. doi:10.1007/978-3-319-10575-8_27.
Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey, and Jirí Srba. Infinite runs in weighted timed automata with energy constraints. In Franck Cassez and Claude Jard, editors, Formal Modeling and Analysis of Timed Systems, 6th International Conference, FORMATS 2008, Saint Malo, France, September 15-17, 2008. Proceedings, volume 5215 of Lecture Notes in Computer Science, pages 33-47. Springer, 2008. doi:10.1007/ 978-3-540-85778-5_4.
Patricia Bouyer, Piotr Hofman, Nicolas Markey, Mickael Randour, and Martin Zimmermann. Bounding average-energy games. In Javier Esparza and Andrzej S. Murawski, editors, Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, volume 10203 of Lecture Notes in Computer Science, pages 179-195, 2017. doi:10.1007/978-3-662-54458-7_11.
Patricia Bouyer, Nicolas Markey, Mickael Randour, Kim G. Larsen, and Simon Laursen. Average-energy games. Acta Inf., 55(2):91-127, 2018. doi:10.1007/s00236-016-0274-1.
Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. Games where you can play optimally with arena-independent finite memory. CoRR, abs/2001.03894, 2020. arXiv:2001.03894.
Romain Brenguier, Lorenzo Clemente, Paul Hunter, Guillermo A. Pérez, Mickael Randour, Jean-François Raskin, Ocan Sankur, and Mathieu Sassolas. Non-zero sum games for reactive synthesis. In Adrian-Horia Dediu, Jan Janousek, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings, volume 9618 of Lecture Notes in Computer Science, pages 3-23. Springer, 2016. doi:10.1007/978-3-319-30000-9_1.
Thomas Brihaye, Florent Delgrange, Youssouf Oualhadj, and Mickael Randour. Life is random, time is not: Markov decision processes with window objectives. In Wan Fokkink and Rob van Glabbeek, editors, 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands, volume 140 of LIPIcs, pages 8:1-8:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.CONCUR.2019.8.
Véronique Bruyère, Emmanuel Filiot, Mickael Randour, and Jean-François Raskin. Meet your expectations with guarantees: Beyond worst-case synthesis in quantitative games. Inf. Comput., 254:259-295, 2017. doi:10.1016/j.ic.2016.10.011.
Véronique Bruyère, Quentin Hautem, and Mickael Randour. Window parity games: an alternative approach toward parity games with time bounds. In Domenico Cantone and Giorgio Delzanno, editors, Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2016, Catania, Italy, 14-16 September 2016, volume 226 of EPTCS, pages 135-148, 2016. doi:10.4204/EPTCS.226.10.
Véronique Bruyère, Quentin Hautem, Mickael Randour, and Jean-François Raskin. Energy mean-payoff games. In Wan Fokkink and Rob van Glabbeek, editors, 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands, volume 140 of LIPIcs, pages 21:1-21:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.CONCUR.2019.21.
Arindam Chakrabarti, Luca de Alfaro, Thomas A. Henzinger, and Mariëlle Stoelinga. Resource interfaces. In Rajeev Alur and Insup Lee, editors, EMSOFT, volume 2855 of Lecture Notes in Computer Science, pages 117-133. Springer, 2003. doi:10.1007/978-3-540-45212-6_9.
Krishnendu Chatterjee and Laurent Doyen. Energy parity games. Theor. Comput. Sci., 458:49-60, 2012. doi:10.1016/j.tcs.2012.07.038.
Krishnendu Chatterjee, Laurent Doyen, Mickael Randour, and Jean-François Raskin. Looking at mean-payoff and total-payoff through windows. Inf. Comput., 242:25-52, 2015. doi: 10.1016/j.ic.2015.03.010.
Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdzinski. Mean-payoff parity games. In 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings, pages 178-187. IEEE Computer Society, 2005. doi: 10.1109/LICS.2005.26.
Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman. Generalized parity games. In Helmut Seidl, editor, Foundations of Software Science and Computational Structures, 10th International Conference, FOSSACS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, March 24-April 1, 2007, Proceedings, volume 4423 of Lecture Notes in Computer Science, pages 153-167. Springer, 2007. doi:10.1007/978-3-540-71389-0_12.
Krishnendu Chatterjee, Mickael Randour, and Jean-François Raskin. Strategy synthesis for multi-dimensional quantitative objectives. Acta Inf., 51(3-4):129-163, 2014. doi:10.1007/ s00236-013-0182-6.
Florent Delgrange, Joost-Pieter Katoen, Tim Quatmann, and Mickael Randour. Simple strategies in multi-objective MDPs. In Armin Biere and David Parker, editors, Tools and Algorithms for the Construction and Analysis of Systems - 26th International Conference, TACAS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25-30, 2020, Proceedings, Part I, volume 12078 of Lecture Notes in Computer Science, pages 346-364. Springer, 2020. doi:10.1007/ 978-3-030-45190-5_19.
Andrzej Ehrenfeucht and Jan Mycielski. Positional strategies for mean payoff games. Int. Journal of Game Theory, 8(2):109-113, 1979.
E. Allen Emerson and Charanjit S. Jutla. The complexity of tree automata and logics of programs. In FOCS, pages 328-337. IEEE Computer Society, 1988. doi:10.1109/SFCS.1988. 21949.
Nathanaël Fijalkow and Florian Horn. The surprizing complexity of reachability games. CoRR, abs/1010.2420, 2010. arXiv:1010.2420.
Nathanaël Fijalkow, Florian Horn, Denis Kuperberg, and Michal Skrzypczak. Trading bounds for memory in games with counters. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 197-208. Springer, 2015. doi:10.1007/978-3-662-47666-6_16.
Hugo Gimbert. Pure stationary optimal strategies in Markov decision processes. In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 200-211. Springer, 2007. doi:10.1007/ 978-3-540-70918-3_18.
Hugo Gimbert and Edon Kelmendi. Two-player perfect-information shift-invariant submixing stochastic games are half-positional. Unpublished, 2014.
Hugo Gimbert and Wieslaw Zielonka. When can you play positionally? In Jirí Fiala, Václav Koubek, and Jan Kratochvíl, editors, Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, volume 3153 of Lecture Notes in Computer Science, pages 686-697. Springer, 2004. doi:10.1007/978-3-540-28629-5_53.
Hugo Gimbert and Wieslaw Zielonka. Games where you can play optimally without any memory. In Martín Abadi and Luca de Alfaro, editors, CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings, volume 3653 of Lecture Notes in Computer Science, pages 428-442. Springer, 2005. doi:10.1007/11539452_33.
Hugo Gimbert and Wieslaw Zielonka. Pure and Stationary Optimal Strategies in Perfect-Information Stochastic Games with Global Preferences. Unpublished, December 2009. URL: https://hal.archives-ouvertes.fr/hal-00438359.
Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002. doi:10.1007/3-540-36387-4.
Marcin Jurdzinski. Deciding the winner in parity games is in UP ∩ co-UP. Inf. Process. Lett., 68(3):119-124, 1998. doi:10.1016/S0020-0190(98)00150-1.
Marcin Jurdzinski, Ranko Lazic, and Sylvain Schmitz. Fixed-dimensional energy games are in pseudo-polynomial time. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 260-272. Springer, 2015. doi:10.1007/ 978-3-662-47666-6_21.
Eryk Kopczyński. Half-positional determinacy of infinite games. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 336-347. Springer, 2006. doi:10.1007/11787006_29.
Eryk Kopczyński. Half-positional Determinacy of Infinite Games. PhD thesis, Warsaw University, 2008.
Donald A. Martin. Borel determinacy. Annals of Mathematics, 102(2):363-371, 1975.
Martin J. Osborne and Ariel Rubinstein. A course in game theory. The MIT Press, Cambridge, USA, 1994.
Mickael Randour. Automated synthesis of reliable and efficient systems through game theory: A case study. In Proc. of ECCS 2012, Springer Proceedings in Complexity XVII, pages 731-738. Springer, 2013. doi:10.1007/978-3-319-00395-5_90.
Stéphane Le Roux. Infinite sequential Nash equilibrium. Logical Methods in Computer Science, 9(2), 2013. doi:10.2168/LMCS-9(2:3)2013.
Stéphane Le Roux. Concurrent games and semi-random determinacy. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 40:1-40:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.MFCS.2018.40.
Stéphane Le Roux and Arno Pauly. Extending finite-memory determinacy to multi-player games. Inf. Comput., 261(Part):676-694, 2018. doi:10.1016/j.ic.2018.02.024.
Stéphane Le Roux, Arno Pauly, and Mickael Randour. Extending finite-memory determinacy by Boolean combination of winning conditions. In Sumit Ganguly and Paritosh K. Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, volume 122 of LIPIcs, pages 38:1-38:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi: 10.4230/LIPIcs.FSTTCS.2018.38.
Yaron Velner, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Alexander Moshe Rabinovich, and Jean-François Raskin. The complexity of multi-mean-payoff and multi-energy games. Inf. Comput., 241:177-196, 2015. doi:10.1016/j.ic.2015.03.001.
Wieslaw Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theor. Comput. Sci., 200(1-2):135-183, 1998. doi:10.1016/S0304-3975(98) 00009-7.