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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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]
Line 39: Line 39:
 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>
 <!-- <!--
Line 61: Line 62:
 </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><!--
Line 73: Line 74:
 --></html> --></html>
  
-8. Ideals in wqos and symbolic algorithms + Revisions before the exam.+**No class on Nov 1st** (holidays). 
 + 
 + 
 +8. Nov2019: Ideals in wqos and symbolic algorithms + Revisions before the exam.
  
 <html><!-- <html><!--
Line 117: Line 121:
  
 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}}
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA