Chennai Mathematical Institute


3.30 pm, Seminar Hall
10th,12th,17th,19th and 24th January 2017 (Tuesdays/Thursdays)
A Short Course on the Algorithmic Aspects of WQO Theory

Philippe Schnoebelen
CNRS and ENS Cachan.



Speaker: Philippe Schnoebelen, CNRS and ENS Cachan

Venue: Seminar Hall, CMI

Time and Date: 3.30pm on 10th,12th,17th,19th and 24th January 2017 (Tuesdays/Thursdays).

TITLE: A Short Course on the Algorithmic Aspects of WQO Theory

Course Details:

Well-quasi-orderings (wqos) are a fundamental tool in logic and computer science. They provide termination arguments in a large number of decidability (or finiteness, regularity, 窶ヲ) results. In constraint solving, automated deduction, program analysis, and many more fields, wqos usually appear under the guise of specific tools, like Dickson窶冱 Lemma (for tuples of integers), Higman窶冱 Lemma (for words and their subwords), Kruskal窶冱 Tree Theorem and its variants (for finite trees with embeddings), and recently the Robertson-Seymour Theorem (for graphs and their minors). What is not very well known is how to analyze the complexity of wqo-based algorithms.

The purpose of this course is to provide an introduction to the algorithmic aspects of wqos: to present generic algorithms working on large classes of problems, to introduce the techniques used to prove complexity upper bounds and lower bounds, to explain the use of wqo ideals in algorithms. It will be divided in five lectures that will try to fit the following outline:

[Lecture 1] Well-quasi-orders (wqos): basics, constructing wqos

[Lecture 2] Wqo-based reasoning: well-structured transition systems (WSTS), termination proofs, ..

[Lecture 3] Fast-growing complexity: definitions, length function theorems for proving upper bounds

[Lecture 4] Fast-growing complexity: Hardy computations for proving lower bounds

[Lecture 5] Ideals of wqos: effective representations and algorithms

Additional Material on the course can be found at