Philippe Schnoebelen - Well-quasi-orderings for progam analysis and computational complexity

Wednesday 16th December 2015 - 10:00 to 11:00 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.