Habilitation Defense
Defense
I defended 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)
Here are the Habilitation Thesis and the slides from the defense (Acrobat Reader is needed in order to play the animations).
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
- On Polynomial Time for Infinite Sets
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
- Mikołaj Bojańczyk
Professor at Universytet Warszawski, Poland (reviewer) - Javier Esparza
Professor at Technische Universität München, Germany (reviewer) - Alain Finkel
Professor at ENS Paris-Saclay, France (examiner) - Géraud Sénizergues
Professor at Université de Bordeaux, France (reviewer) - Andreas Weiermann
Professor at Universiteit Gent, Belgium (examiner) - James B. Worrell
Professor at the University of Oxford, UK (examiner)
Access Information
From the Bagneux station of RER B:
The Daniel Chemla amphitheater is located underground in the Institut d'Alembert building:
