Games on Graphs: From Logic and Automata to Algorithms
arXiv:2305.10546
Abstract
The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared in the study of automata and logic, and they later became important for program verification and synthesis. They have many more applications, in particular some of the models investigated in this book were introduced and studied in neighbouring research communities such as optimisation, reinforcement learning, model theory, and set theory.
621 pages. Coordinator: Nathanaël Fijalkow
References in corpus (17)
- Qualitative Analysis of Partially-observable Markov Decision Processes
- Succinct progress measures for solving parity games
- Markov Decision Processes with Multiple Long-run Average Objectives
- Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time
- Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
- Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
- Games Where You Can Play Optimally with Arena-Independent Finite Memory
- Window Parity Games: An Alternative Approach Toward Parity Games with Time Bounds
- Perfect Half Space Games
- Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs
- Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes
- How do we remember the past in randomised strategies?
- Characterizing Positionality in Games of Infinite Duration over Infinite Graphs
- The Theory of Universal Graphs for Infinite Duration Games
- Energy mean-payoff games
- Optimal bounds for bit-sizes of stationary distributions in finite Markov chains
- Universal Complexity Bounds Based on Value Iteration for Stochastic Mean Payoff Games and Entropy Games