Games on Graphs

From Logic and Automata to Algorithms

Buch | Hardcover

600 Seiten

2026
Cambridge University Press (Verlag)
978-1-009-50068-5 (ISBN)

Noch nicht erschienen (ca. April 2026)
Versandkostenfrei
Auch auf Rechnung

Artikel merken

This accessible tutorial reference by a multidisciplinary team of experts surveys efficient algorithms for analysing different types of games on graphs and applications in optimisation, reinforcement learning, model theory, and set theory. Prerequisites are a basic understanding of discrete algorithms and graph theory.

This volume introduces the fundamental results and the state of the art in infinite duration games on graphs. These versatile game models first appeared in the study of automata and logic, but later became important for program verification and synthesis. They have many more applications. In particular, this book covers models from the fields of optimisation, reinforcement learning, model theory, and set theory. The material is presented at a level accessible to beginning graduate students, requiring only a basic understanding of discrete algorithms and graphs. The book's primary objective is constructing efficient algorithms for analysing different types of games. Rather than describe their implementation in full detail, it investigates their theoretical foundations and proves their properties and winning strategies. This tutorial reference from experts across the field is ideal for students, researchers, and professionals in logic and automata, verification and synthesis, and related fields.

Nathanaël Fijalkow is Director of Research at CNRS, LaBRI, University of Bordeaux. He has been on games on graphs for over a decade and contributed to some of the field's most important recent results. He has taught games on graphs at several universities (Paris, Warsaw, Bordeaux) and been heavily involved in organising scientific events on the topic.

List of contributors; Preface; 1. Introduction Nathanaël Fijalkow; I. Classic: 2. Parity games John Fearnley and Nathanaël Fijalkow; 3. Regular games Nathanael Fijalkow and Florian Horn; 4. Positionality and memory Antonio Casares, Pierre Ohlmann and Pierre Vandenhov; 5. Games with payoffs Nathanaël Fijalkow and Benjamin Monmege; II. Stochastic: 6. Markov decision processes Petr Novotný; 7. Stochastic games Nathalie Betrand, Patricia Bouyer and Nathanaël Fijalkow; III. Information: 8. Concurrent games Rasmus Ibsen-Jensen; 9. Games with signals Hugo Gimbert; 10. Synchronous distributed games C. Aiswarya, Paul Gastin and Nathalie Sznajder; IV. Infinite: 11. Timed games Nicolas Markey and Ocan Sankur; 12. Pushdown games Arnaud Carayol and Olivier Serre; 13. Games with counters Sylvain Schmitz; V. Multi: 14. Games with multiple objectives Mickael Randour; 15. Multiplayer games Romain Brenguier and Ocan Sankue; 16. Bidding games Guy Avni and Thomas A. Henzinger; Bibliography.

Erscheint lt. Verlag	30.4.2026
Zusatzinfo	Worked examples or Exercises
Verlagsort	Cambridge
Sprache	englisch
Themenwelt	Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
	Mathematik / Informatik ► Informatik ► Theorie / Studium
	Mathematik / Informatik ► Mathematik
ISBN-10	1-009-50068-6 / 1009500686
ISBN-13	978-1-009-50068-5 / 9781009500685
Zustand	Neuware