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é:   
The Reachability Problem for Petri Nets is Not Elementary
du groupe Séminaire Méthodes Formelles

Date 2018-11-06  11:00-12:00
TitreThe Reachability Problem for Petri Nets is Not Elementary 
RésuméPetri nets, also known as vector addition systems, are a long established and widely used model of concurrent processes. The complexity of their reachability problem is one of the most prominent open questions in the theory of verification. That the reachability problem is decidable was established by Mayr in his seminal STOC 1981 work, and the currently best upper bound is non-primitive recursive cubic-Ackermannian of Leroux and Schmitz from LICS 2015. We show that the reachability problem is not elementary. Until this work, the best lower bound has been exponential space, due to Lipton in 1976. Joint work with Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Filip Mazowiecki. 
Lieu178 
OrateurJérôme Leroux 
Emailhttp://www.labri.fr/perso/leroux/ 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index