Never-ending Games

List of available topics:

• Small-progress measures for solving parity games
  Literature:
  • Marcin Jurdzinski: Small Progress Measures for Solving Parity Games
  • Grädel, Thomas, Wilke: Automata, Logics, and Infinite Games (Chapter 7)
  
  
• Memoryless determinacy of parity games and Zielonka's algorithm.
  Literature:
  • Wieslaw Zielonka: Infinite Games on Finitely Coloured Graphs with Applications to Automata on Infinite Trees
  • Grädel, Thomas, Wilke: Automata, Logics, and Infinite Games (Chapter 6)
  • Perrin and Pin: Infinite Words (Chapter IV.4)
  
  
• Reducing parity games to linear programming.
  Literature:
  • Sven Schewe: From Parity and Payoff Games to Linear Programming
  
  
• Generalized parity games.
  Literature:
  • Krishnendu Chatterjee, Thomas A. Henzinger, Nir Piterman: Generalized Parity Games
  
  
• Mean-payoff games: Comparison of two strategy improvement/policy iteration algorithms (two topics).
  Literature:
  • Henrik Björklund, Sven Sandberg, Sergei G. Vorobyov: A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games
  • Vishesh Dhingra, Stéphane Gaubert: How to solve large scale deterministic games with mean payoff by policy iteration
  
  
• Energy games: Reduction from mean-payoff games and algorithms for solving them.
  Literature:
  • Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey, Jirí Srba: Infinite Runs in Weighted Timed Automata with Energy Constraints
  • Lubos Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini, Jean-François Raskin: Faster algorithms for mean-payoff games
  • Lubos Brim, Jakub Chaloupka: Using Strategy Improvement to Stay Alive
  
  
• Generalized mean-payoff and energy games.
  Literature:
  • Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Jean-François Raskin: Generalized Mean-payoff and Energy Games
  
  
• Solving games of imperfect information.
  Literature:
  • Martin De Wulf, Lauren Doyen, Jean-François Raskin: A Lattice Theory for Solving Games of Imperfect Information
  
  
• Rabin games and LTL synthesis
  Literature:
  • Nir Piterman, Amir Pnueli: Faster Solutions of Rabin and Streett Games
  • Lily
  
  
• Muller games.
  Literature:
  • John Fearnley, Martin Zimmermann: Playing Muller Games in a Hurry
  
  
• LTL games.
  Literature:
  • Aidan Harding, Mark Ryan, Pierre-Yves Schobbens: A New Algorithm for Strategy Synthesis in LTL Games
  
  
• Control of hybrid systems: discrete abstractions for continuous-state systems.
  Literature:
  • Paulo Tabuada: Verification and Control of Hybrid Systems (Chapter 6)
  
  
• AbsSynthe: abstract synthesis.
  Literature:
  • Romain Brenguier, Guillermo A. Péerez, Jean-François Raskin, Ocan Sankur: AbsSynthe: abstract synthesis from succinct safety specifications (Slides)
  
  
• Acacia+: LTL synthesis with mean-payoff objectives.
  Literature:
  • Aaron Bohy, Véronique Bruyère, Emmanuel Filiot, Jean-François Raskin: Synthesis from LTL Specifications with Mean-Payoff Objectives
  • Acacia+