Chennai Mathematical Institute

Silver Jubilee Events

CMI Silver Jubilee Lecture

Philippe Schnoebelen, LSV, ENS Cachan, France

Basics of WQO theory, with some applications in computer science

Monday, February 23, 2015


Well-quasi-orderings (WQOs) are a fundamental tool in logic, graph theory, combinatorics, computer science, … In computer science, they provide termination arguments in a large number of decidability (or finiteness, regularity, …) results. In these applications, WQOs usually appear under the guise of specific tools, like Dickson's Lemma (for tuples of natural numbers), Higman's Lemma (for sequences), Kruskal's Tree Theorem and its variants (for finite trees with embeddings), and recently the Robertson-Seymour Theorem (for graphs and their minors).

The lecture will recall in a gentle way the most basic notions and results of WQO theory, and describe some applications or open problems that come from a computer science perspective.