Evènement pour le groupe Modélisation et Verification

Date 2009-03-12  11:00-12:15
TitreHow to get decidability of distributed synthesis ? 
RésuméThe distributed synthesis problem is to come up with a local strategy for each process such that the resulting behaviours of the system meet a given specification. Our general aim is to define natural conditions under which synthesis or control are decidable for distributed systems. It is known that these problems are undecidable for most synchronous systems. So in this work we study asynchronous systems which communicate through signals -- actions that are immediately received by the target process. Another main cause of undecidability comes from the specifications. Here, we consider emph{external} specifications over emph{partial orders}. External means that specifications only relate input and output actions from and to the environment and not internal signals exchanged by processes. We also ask for some natural closure properties of the specification. We obtain decidability for the subclass of networks where communication happens through a strongly connected graph. We believe that this framework for distributed synthesis yields decidability results for many more architectures.  
LieuSalle 076, LaBRI, Rez-de-chaussée 
OrateurPaul Gastin 
UrlLSV, Cachan, France 

Aucun document lié à cet événement.

Retour à l'index