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 Fridays from 8h45 to 11h45, starting on September 20th, building Sophie Germain room 1004.

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 Sylvain Schmitz, IRIF, Université Paris-Cité

Other members of the teaching team: Ph. Schnoebelen, LMF, ENS Paris-Saclay, Université Paris-Saclay & CNRS.

Responsable / In charge: Jean Goubault-Larrecq

Midterm Exam: Will be given as a homework assignment at the end of the fourth lecture (October 11th). Here is the homework assignment for 2022 as an example, with a possible solution.

Final Exam: Final week of November. Here are the exam questions and some solutions of the 2023 edition.

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.

Lecture notes

1. 20 Sep. 2024 (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. 27 Sep. 2024: 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. 04 Oct. 2024: 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. 11 Oct. 2024: Return of Dickson: Application to polynomial systems, Gröbner bases, and Buchberger's algorithm; the slides (with animations), and the short slides (without animations). Beyond trees: graph minors, and the Robertson and Seymour theorem (no proof). Applications to algorithmic graph theory. (If time permits: beyond wqos: bqos, Noetherian spaces; (order-)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. 18 Oct. 2024 (S. Schmitz) Long bad sequences (Section 2.1). Ordinals and ordinal notations, subrecursive functions (Appendix A). Complexity classes beyond ELEMENTARY (Appendix B and article). Exercises: 2.2, 2.3, 2.13, 2.11, 2.15.

6. 25 Oct. 2024: Lossy counter machines (cheat sheet). Hardness: boundedness is undecidable, reachability and coverability are Ackermann-hard (Chapter 3, article). Exercises: 3.1, 3.2, 3.3, 3.4.

7. 08 Nov. 2024: Complexity upper bounds: normed wqos, controlled bad sequences. The case of ordinals (article, habilitation). Polynomial wqos (Chapter 2, habilitation). Reachability and coverability in lossy counter machines are in Ackermann (Chapter 2, article). Exercises: 2.1, 2.12

8. 15 Nov. 2024: Ideals of wqos: Finer upper bounds through monotone descending chains (Chapter 4, article).

9. 22 Nov. 2024: Final written 2-hour exam. No documents allowed. Here are the exam questions for 2024, with some solutions.

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

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

Main related courses:

• Advanced techniques of verification, where wqos are being used, too
• Algorithmic Verification of Programs, where wqos are being used, too
• Parameterized algorithms and complexity: the algorithms we will see in database theory and in graph theory are a natural introduction to the notion of parameterized complexity.

Other related courses:

• Polynomial systems, computer algebra, and applications: the computation of Gröbner bases is based on Dickson's lemma, one of the first results we will see
• Advanced Graph Theory: we will mention the Robertson-Seymour theorem, on well-ordering graphs by minors, and it will be important in the advanced graph theory course.