|2nd Workshop on Games for Design, Verification and Synthesis|
Colocated with CONCUR'10
Paris (France), 4 September 2010
GASICS is an ESF project of the EUROCORES programme LogICCC (Modelling intelligent interaction – Logic in the Humanities, Social and Computational sciences ). It studies game theoretic formalizations of interactive computational systems and algorithms for their analysis and synthesis. Our aim is to extend the existing notions of games played on graphs introduced by computer scientists. Currently, most of the games played on graphs are of the sort "two-player zero-sum", we aim to extend them to "multiple-player non-zero-sum", and show the applicability of the new theory to the analysis and synthesis of interactive computational systems.
The aim of this workshop is to bring together researchers working on game-related subjects, and to discuss on various aspects of game theory in the fields where it is applied. The workshop will be composed of two invited talks, together with contributed talks on the following (non-exhaustive) list of relevant topics:
- Adapted notions of games for synthesis of complex interactive computational systems
- Games played on complex and infinite graphs
- Games with quantitative objectives
- Game with incomplete information and over dynamic structures
- Heuristics for efficient game solving.
- Krishnendu Chatterjee:
Games with Finitary Parity and Streett ObjectivesIn this talk we will present games with finitary parity and Streett objectives. The class of finitary objectives is a stronger condition than classical ω-regular conditions, and we will discuss how it gets rid of certain weakness of classical infinitary formulation. In this talk we will present results related to determinacy of these games, present algorithms and complexity for solving these games, and characterize the memory requirements of winning strategies. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound.
- Antonín Kučera:
Stochastic games with timeStochastic turn-based games can be seen as discrete-time Markov chains extended by non-deterministic vertices where the players can make their decisions. Similarly, one can consider game-theoretic extensions of stochastic processes with continuous time, such as continuous-time Markov chains, semi-Markov processes, or even generalized semi-Markov processes. In the talk we give an overview of recent results about this type of games.
|09:25 - 09:30||Welcome — Introduction|
|09:30 - 10:30||Krishnendu Chatterjee (invited talk)|
|10:30 - 11:00||Coffee break|
|11:00 - 11:30||Olivier Finkel.|
|11:30 - 12:00||Rüdiger Ehlers.|
|12:00 - 12:30||Loïs Vanhée and Sophie Pinchinat.|
|12:30 - 14:00||Lunch|
|14:00 - 15:00||Antonín Kučera (invited talk)|
|15:00 - 15:30||Evgeny Dantsin and Sergei Soloviev.|
|15:30 - 16:00||Coffee break|
|16:00 - 16:30||Catalin Dima, Constantin Enea, Dimitar Guelev and Ferucio Tiplea.|
|16:30 - 17:00||Franck Cassez, Alexandre David, Kim G. Larsen, Jean-François Raskin and Pierre-Alain Reynier.|
|17:00 - 17:30||Nicolas Markey and Pierre-Alain Reynier|
|17:30 - 17:31||Closing|
- Véronique Bruyère
- Marcin Jurdziński
- Kim G. Larsen
- Nicolas Markey
- Jean-François Raskin
- Pierre-Yves Schobbens
- Olivier Serre
- Wolfgang Thomas
Page maintained by Nicolas Markey.
Last modified: 21 September 2010.