Course contents


Reference Material

Topics covered

Date      Topics covered
Jan 5   Introduction, course outline (PDF).
Jan 8   Petri nets, basic definitions, examples, dynamics of a net, token game, elementary net systems, place/transition nets. ( reference A and B)
Jan 12   Elementary net systems, Marking graph, Fundamental situations: Concurrency, Conflict, Causality, Contact. ( reference A and B)
Jan 15   Fundamental situations: Confusion; symmetric and asymmetric confusion. Subclasses of nets: sequential nets, marked graphs. ( reference A and B)
Jan 19   Free-choice nets, extended free-choice nets and behavioural free-choice nets ( reference D)
Jan 22   Behaviour of net systems: firing sequences, traces ( reference A and B)
Jan 25   Behaviour of net systems: posets ( Reference B)
Jan 27   Behaviour of net systems: extending traces, compatibility and poset on traces ( Reference B)
Feb 09   Place/Transition (Petri) nets, basic definitions and properties. ( reference C)
Feb 12   Quiz 1
Feb 16   Petri nets: Boundedness, reachability, liveness, coverability problems. Omega-firing sequences, coverability tree. ( reference C)
Feb 19   Petri nets: Finiteness of coverability trees, Dickson's lemma. ( reference C)
Feb 22   Midsem week
Feb 25   Midsem week
Mar 01   Quasi orders and well quasi orders ( reference E and F)
Mar 04   Well-structured transition systems, different notions of compatibility( reference E)
Mar 08   Finite reachability tree construction for termination problem for WSTS, effectivity conditions ( reference E)
Mar 09   Backward set saturation technique and decidability of coverability ( reference E)
Mar 11   Message passing systems and lossy channel systems ( reference E)
Mar 15   Higman's lemma, its proof and decidability results for lossy channel systems ( reference E and F)
Mar 15   Quiz 2
Mar 18   Broadcast protocols and a lower bound on the complexity of termination algorithm (Quiz 2 and reference F)
Mar 20   Course presentations
Mar 21   Course presentations
Mar 29   Complexity of WSTS: definitions, a new complexity hierarchy (Chapter 2 of reference F)
Apr 01   Complexity of WSTS: finding upper-bounds, statement of the length function theorem (Chapter 2 of reference F)
Apr 05   More examples and results for upper-bounds, reductions (Chapter 2 of reference F)
Apr 08   A strategy for finding lower-bounds: examples and some results. (Chapter 3 of reference F)
Apr 12   Other formal models for concurrency: products of automata ( reference G)