cours:c-2-9-1 [2019/09/03 14:18] phs [Evaluation exam] |
cours:c-2-9-1 [2019/10/22 16:38] (current) phs [Outline of the course] |

| Exercises for next time: 1.1, 1.2, 1.3, 1.22, 1.13, 1.14. | | Exercises for next time: 1.1, 1.2, 1.3, 1.22, 1.13, 1.14. |

| | | |

- | 2. Petri nets continued. Dickson's original application. Our second operation on wqos: Higman's Lemma. Applications: lossy channel systems. The {{cours:upload:slides-2-9-1-cours2.pdf|slides}}. | + | 2. **20 Sep. 2019: **Petri nets continued. Dickson's original application. Our second operation on wqos: Higman's Lemma. Applications: lossy channel systems. The {{cours:upload:slides-2-9-1-cours2.pdf|slides}}. |

- | Exercises for next time: 1.6, 1.9**, 1.15 (oops, sorry, no: next time)**, 1.29. | + | Exercises for next time: 1.6, 1.9, 1.29. |

| | | |

| | | |

- | 3. 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 {{cours:upload:slides-2-9-1-cours3.pdf|slides}}. | + | 3. **27 Sep. 2019: **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 {{cours:upload:slides-2-9-1-cours3.pdf|slides}}. |

| Exercises for next time: 1.15, 1.5, 1.7, 1.8, 1.10, 1.11, 1.12. | | Exercises for next time: 1.15, 1.5, 1.7, 1.8, 1.10, 1.11, 1.12. |

| | | |

| | | |

- | 4. 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 {{cours:upload:slides-2-9-1-cours4.pdf|slides}}. | + | 4. **4 Oct. 2019: **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 {{cours:upload:slides-2-9-1-cours4.pdf|slides}}. |

| | | |

| + | {{cours:upload:dm-2-9-1-2019.pdf|The homework assignment and midterm exam}}, to turn in either to Philippe Schnoebelen or by email to [[mailto:goubault@lsv.fr|Jean Goubault-Larrecq]], by October 18th, 2019, 8h30am CEST sharp. |

| <html><!-- | | <html><!-- |

- | {{cours:upload:dm-2-9-1-2018.pdf|The homework assignment and midterm exam}}, to turn in either to Philippe Schnoebelen or by email to [[mailto:goubault@lsv.fr|Jean Goubault-Larrecq]], by October 22nd, 2018, 16h15 sharp. | |

| A {{cours:upload:dm-2-9-1-2018-ans.pdf|possible solution}}. | | A {{cours:upload:dm-2-9-1-2018-ans.pdf|possible solution}}. |

| --></html> | | --></html> |

| + | |

| <html> | | <html> |

| <!-- | | <!-- |

| </html> | | </html> |

| | | |

- | 5. 11 Oct. 2019 (Ph. Schnoebelen): Lossy channel systems and decidability (Sections 1.9 and 3.1). See also [[http://www.lsv.fr/**~phs**/**publis-phs.php?onlykey=**phs-rp10|this paper]]. | + | 5. 11 Oct. 2019 (Ph. Schnoebelen): Lossy channel systems and decidability (Sections 1.9 and 3.1). See also [[http://www.lsv.fr/**Publis/PAPERS/PDF**/phs-rp10**.pdf**|this paper**]]. NB: Students interested in Presburger arithmetic will learn a lot by reading [[https://dl.acm.org/citation.cfm?id=3242964|this recent survival guide**]]. |

| | | |

- | 6. Lossy counters are hard (Section 3): existence of Büchi runs is undecidable, reachability is Ackermann-hard. | + | 6. **18 Oct. 2019: **Lossy counters are hard (Section 3): existence of Büchi runs is undecidable, reachability is Ackermann-hard. |

| | | |

- | 7. Complexity Upper Bounds for WSTS (Section 2): Normed wqos and controlled bad sequences. The Length Function Theorem for polynomials nwqos. | + | 7. **25 Oct. 2019: **Complexity Upper Bounds for WSTS (Section 2): Normed wqos and controlled bad sequences. The Length Function Theorem for polynomials nwqos. |

| | | |

| <html><!-- | | <html><!-- |

| --></html> | | --></html> |

| | | |

- | 8. Ideals in wqos and symbolic algorithms + Revisions before the exam. | + | ****No class on Nov 1st** (holidays). ** |

| + | ** ** |

| + | ** ** |

| + | **8. **8 **Nov**. **2019: **Ideals in wqos and symbolic algorithms + Revisions before the exam. |

| | | |

| <html><!-- | | <html><!-- |

| | | |

| The evaluation is in two parts : a homework assignment serving as midterm exam, and a final 3-hour written exam (date to be agreed with the class). | | The evaluation is in two parts : a homework assignment serving as midterm exam, and a final 3-hour written exam (date to be agreed with the class). |

| + | |

| + | <html> |

| + | <!-- |

| + | The {{cours:upload:dm-2-9-1-2019.pdf|homework assignment}} for this year, to be turned it by October 18th, 2019, to Jean Goubault-Larrecq or to Philippe Schnoebelen. |

| + | --> |

| + | </html> |

| | | |

| Here are {{cours:upload:dm-2-9-1-2018.pdf|last year's homework assignment}} | | Here are {{cours:upload:dm-2-9-1-2018.pdf|last year's homework assignment}} |