moteur de recherche

Séminaire Algo - Sylvain Schmitz
Séminaire Algo - Sylvain Schmitz
26-Mar-2019 14:00
Age: 28 days

Sylvain Schmitz

The complexity of reachability in vector addition systems

Seminar room 4B125 (Copernic building)

Abstract: The last few years have seen a surge of decision problems with an astronomical, non primitive-recursive complexity, in logic, verification, and games. While the existence of such uncontrived problems is known since the early 1980s, the field has matured with techniques for proving complexity lower and upper bounds and the definition of suitable complexity classes. This framework has been especially successful for analysing so-called `well-structured systems'---i.e., transition systems endowed with a well-quasi-order, which underly most of these astronomical problems---, but it turns out to be applicable to other decision problems that resisted analysis, including two famous problems: reachability in vector addition systems and bisimilarity of pushdown automata. 

In this talk, I will explain how some of these techniques apply toreachability in vector addition systems, a landmark result in theoretical computer science, with applications in an array of fields ranging from program verification to data logics. The decidability of the problem was first shown by Mayr thanks to a decomposition algorithm. I will present succinctly the main ideas behind a tight Ackermannian complexity upper bound obtained with Jérôme Leroux for this algorithm.

<- Back to: Accueil