Habilitation Defense

Defense

I will defend my habilitation thesis titled Algorithmic Complexity of Well-Quasi-Orders on

Date
Monday, November 27 2017 at 02:00pm
Place
Daniel Chemla amphitheater (Institut d'Alembert)
Speaker
Sylvain Schmitz

The manuscript is available here.

Seminars

Two additional seminars will be given by members of the jury:

Date
Monday, November 27 2017 at 11:00am
Place
Salle Renaudeau (Bâtiment Laplace)
Speaker
Andreas Weiermann (Ghent University)
Title
Generalized Goodstein sequences
Date
Tuesday, November 28 2017 at 11:00am
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Mikołaj Bojańczyk (University of Warsaw)
Title
TBA

Abstract

This document is dedicated to the algorithmic complexity of well-quasi-orders, with a particular focus on their applications in verification, where they allow to tackle systems featuring an infinite state-space, representing for instance integer counters, the number of active threads in concurrent settings, real-time clocks, call stacks, cryptographic nonces, or the contents of communication channels.

The document presents a comprehensive framework for studying such complexities, encompassing the definition of complexity classes suitable for problems with non-elementary complexity and proof techniques for both upper and lower bounds, along with several examples where the framework has been applied successfully. In particular, as a striking illustration of these applications, it includes the proof of the first known complexity upper bound for reachability in vector addition systems and Petri nets.

Jury

Access Information

From the Bagneux station of RER B:

The Daniel Chemla amphitheater is located underground in the Institut d'Alembert building:

Institut Alembert, ENS Cachan

About LSV