Date: Wed, 11 May 2011 16:28:40 +0200 (CEST)
From: Bas Basten
To: sen1-list
Subject: SEN1 Meeting tomorrow: Sunil Simon

Dear all,

Tomorrow we will have our next SEN1 Meeting. Sunil will give a talk about his research:

Title: On reactive systems and games of infinite duration.

Abstract:
A well known instance of the synthesis problem for reactive systems
asks whether it is possible to construct a finite state input-output
machine which satisfies a regular specification. One challenging
variation is the case of distributed synthesis where a network of
finite state machines need to be synthesised. Distributed synthesis
can easily be seen to be equivalent to the strategy synthesis problem
in multi-player imperfect information games of infinite
duration. Unfortunately, for the general class of imperfect
information games, most of the interesting algorithmic questions like
determining the winning strategy and synthesis of an equilibrium
profile are undecidable. Thus a natural question would be to ask
whether there are decidable subclasses of imperfect information
games. In this context, it seems helpful to view imperfect information
as being generated explicitly by communication between players. We
show that when communication is by means of public announcements many
of the algorithmic questions become decidable.

We start at 10:00 in room L016. See you all there!

Cheers,
Bas