Partager cette page :

Pushdown Vector Addition Systems

le 14 mars 2017

13h45

ENS Rennes, Salle du conseil
Plan d'accès

Intervention de Jérôme Leroux (CNRS/LaBRI, Bordeaux), dans le cadre des séminaires du département Informatique et télécommunications.

Séminaire Informatique et télécommunications

Séminaire Informatique et télécommunications

In this presentation, we overview classical results about vector addition systems, and we present the boundedness and termination problems for vector addition systems equipped with one stack. We then introduce an algorithm, inspired by the Karp & Miller algorithm, that solves both problems. We show that the worst-case running time of this algorithm is hyper-Ackermannian. This is a joint work with M. Praveen, Grégoire Sutre and Patrick Totzke.
Thématique(s)
Formation, Recherche - Valorisation
Contact
David Cachera & François Schwarzentruber

Mise à jour le 31 mars 2017