Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Aspects Algorithmiques de la Théorie des Beaux préordres / Algorithmic Aspects of WQO Theory (24h, 3 ECTS)

Où, quand ? / Where, when?: In 2023, the course takes place on Mondays from 16h15 to 19h15, starting on September 18th, building Sophie Germain room 1002.

Poly / Lecture notes: can be found at this link Algorithmic Aspects of WQO Theory.

Prérequis / Prequisites: Elementary notions from logic (ordinals, ..), from complexity, and from recursion theory.

Intervenants / Lecturers: Jean Goubault-Larrecq (LMF, ENS Paris-Saclay, Université Paris-Saclay) Ph. Schnoebelen, (LMF, ENS Paris-Saclay, Université Paris-Saclay & CNRS)

Responsable / In charge: Jean Goubault-Larrecq

Final Exam / 20 Nov. 2023, 16h30-18h30: Here are the exam questions and some solutions.

Motivations & Abstract

Well-quasi-orderings, or WQOs, play a fundamental role in important results in several areas of computer science : formal language theory, rewriting, program verification, algorithmic graph theory, automated deduction, etc. and they are still intensively used nowadays (see e.g. Separability via Piecewise-Testable Languages by Goubault-Larrecq & Schmitz, or Ordinal-Recursive Complexity by Schmitz & Schnoebelen).

The objective of this course is to teach the basic notions of WQO Theory, motivated and illustrated by algorithmic applications in various areas.

Outline of the course

1. 18 Sep. 2023 (J. Goubault-Larrecq): Introduction. Definition, a few characterizations of wqos. A library of well quasi-ordered data types: announcement, and proofs for the simplest cases. All the other cases will be seen in further lectures. Our first wqo: Dickson's Lemma. Application to coverability of WSTS, and of Petri nets in particular. The slides (with animations), and the short slides (without animations). Exercises for next time: 1.1, 1.2, 1.3, 1.22, 1.13, 1.14.

2. 25 Sep. 2023: Petri nets continued. Dickson's original application. Our second operation on wqos: Higman's Lemma. Applications: lossy channel systems. The slides (with animations), and the short slides (without animations). Exercises for next time: 1.6, 1.9, 1.29.

3. 02 Oct. 2023: Multisets, finite sets, Rado's counterexample. Van der Meyden's algorithm for satisfiability of disjunctive queries on indefinite databases. A quick word on parameterized complexity. Kruskal's theorem. Application to the termination of rewriting systems. The slides (with animations), and the short slides (without animations). Exercises for next time: 1.15, 1.5, 1.7, 1.8, 1.10, 1.11, 1.12. (Do not attempt to do the final subquestion of 1.8. Otherwise, look at the 2018 homework assignment and midterm exam, section 2, for inspiration.)

4. 09 Oct. 2023: Beyond trees: graph minors, and the Robertson and Seymour theorem (no proof). Applications to algorithmic graph theory. Beyond wqos: bqos, Noetherian spaces. Ideals and irreducible (downwards-)closed subsets. The slides (with animations), and the short slides (without animations).

There will be a homework assignment at this point.

5. 16 Oct. 2023 (Ph. Schnoebelen): Lossy counter machines and decidability (Sections 1.9 and 3.1). See also this paper. NB: Students not familiar with Presburger arithmetic will learn a lot by reading this recent survival guide.

6. 23 Oct. 2023 : Verification of Lossy counter machines is hard! Existence of Büchi runs and boundedness are undecidable for LCMs (see this paper). Reachability and coverability are decidable for LCMs but these problems are Ackermann-hard (Sections 3.2—3.4).

People interested in playing with Ackermann's function can try to solve Project Euler's pb 282. If you don't know how to even start to solve this puzzle, you can get ideas by solving pb 188 (a simpler version) or you can ask me for tips in class and I'll be happy to help.

7. 06 Nov. 2023 : Complexity Upper Bounds for WSTS (Section 2): Normed wqos and controlled bad sequences. The Length Function Theorem for polynomials nwqos. NB: The Fast-Growing Complexity Hierarchy is described in this recent article.

8. 13 Nov. 2023 : Exercise 2.16: let us compute Lg,ℕ2(2) assuming g(n)=n+1: this uses two heuristics that limit the search space. Ideal-based representation of down sets (Section 4.1, Examples and motivations can be found in section 2 of this paper).

9. 20 Nov. 2023: Final written 2-hour exam. No documents allowed. Here are the exam questions for this year as well as some solutions.


The evaluation is in two parts : a homework assignment serving as midterm exam, and a final written exam.

Here is this year's (2023) homework assignment, to be turned in by email to Jean Goubault-Larrecq at or before Tuesday, October 24th, 2023.

Here are a past homework assignment and a past final exam.

Related courses

Main related courses:

Other related courses:

Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA