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_ω^ω.  
OrateurM. Praveen 

Aucun document lié à cet événement.

Retour à l'index