Evènement pour le groupe
Modélisation et Verification
Date | 2013-11-21 11:00-12:00 |
Titre | Hyper 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_ω^ω.
|
Lieu | 076 |
Orateur | M. Praveen |
Email | pmanjuna@labri.fr |
Url | LaBRI |
Aucun document lié à cet événement.
RetourRetour à l'index