skip to content
 

Well-quasi-orderings for progam analysis and computational complextiy

Presented by: 
P Schnoebelen CNRS (Centre national de la recherche scientifique)
Date: 
Wednesday 16th December 2015 - 10:00 to 11:00
Venue: 
INI Seminar Room 1
Abstract: 
Co-author: Sylvain Schmitz (ENS Cachan)

The talk will survey some of the applications of well-quasi-orderings in computer science. Well-quasi-orderings are an important tool in some areas like program verification, or computer-aided deduction and theorem-proving. Most importantly, they provide easy proofs for the decidability of logical or combinatorial problems. Recent work by the authors aim at extracting computational complexity bounds from decidability proofs that rely on well-quasi-orderings.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons