Evènement pour le groupe Modélisation et Verification


Date 2013-11-21  11:00-12:00
TitreHyper Ackermannian Bounds for Pushdown Vector Addition Systems 
RésuméWe study the complexity of deciding boundedness of Well Structured Transition Systems equipped with a stack. We introduce a general scheme of induction for bounding lengths of bad nested words over a well quasi ordered set. We use this scheme to show that lengths of bad nested words over vectors of natural numbers is bounded by a function in the class F_ω^ω of the extended Gregorczyk hierarchy. This upper bound is used to derive an upper bound for the running time of an algorithm we give, which is an extension of the classical Karp & Miller algorithm for deciding boundedness. We give a matching lower bound to show that the worst case running time of this extended algorithm can not be below F_ω^ω.  
Lieu076 
OrateurM. Praveen 
Emailpmanjuna@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index