Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Sound negotiations and static analysis
du groupe Séminaire Méthodes Formelles

Date 2016-12-13  11:00-12:00
TitreSound negotiations and static analysis 
RésuméNegotiations are a graphical formalism for describing multiparty distributed cooperation, proposed by Desel and Esparza. Alternatively, they can be seen as a model of concurrency with synchronized choice as communication primitive. Well-designed negotiations must be sound, meaning that, whatever its current state, the negotiation can still be completed. In a former paper, Esparza and Desel have shown that deciding soundness of arbitrary negotiations is PSPACE-complete, and in PTIME for deterministic negotiations. They also considered an intermediate subclass of non-deterministic negotiations, but left the complexity of the soundness problem open. We first consider the soundness problem beyond deterministic negotiations: we show that soundness of acyclic, weakly non-deterministic negotiations is in PTIME, and that checking soundness is already NP-complete for slightly more general classes. Then we show how to use our algorithmic results to provide polynomial algorithms for some analysis problems of workflow nets with data. Joint work with J. Esparza, D. Kuperberg and I. Walukiewicz 
Lieu178 
OrateurAnca Muscholl 
Emailanca@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index