• In this course, we consider different abstract formalisms to model distribution, concurrency and communication. We also focus on systems that can exhibit infinite behaviours and how to reason about them. The course outline can be found here.

• Automata theory (CS208 or equivalent) and Discrete Structures (CS207 or equivalent).

1. Elementary Net Systems (PDF),
   Grzegorz Rozenberg and Joost Engelfriet,
   Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Springer LNCS 1491 (1998) 12-121.

2. Some Behavioural Aspects of Net Theory (PDF),
   P.S. Thiagarajan,
   Theoretical Computer Science, 71 (1990) 133-153.

3. Place/Transition Nets (PDF),
   Jörg Desel and Wolfgang Reisig,
   Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Springer LNCS 1491 (1998) 122-173.

4. Structure theory of Petri nets: the free choice hiatus (PDF),
   E. Best,
   Advances in Petri nets 1986-87, part 1 on Petri nets , Springer LNCS 254 168-205.

5. Well-Structured Transition Systems Everywhere! (PDF),
   Alain Finkel and Philippe Schnoebelen,
   Theoretical Computer Science 256(1-2), pages 63-92, 2001.

6. Algorithmic Aspects of WQO Theory (PDF),
   Sylvain Schmitz and Philippe Schnoebelen,
   Lecture notes for MPRI Masters' course, France 2012.

7. Automata on Distributed Alphabets (PDF,PDF 2-in-1)
   Madhavan Mukund,
   In Deepak D'Souza and Priti Shankar (eds),
   Modern Applications of Automata Theory, World Scientific.

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)