Course contents
 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.
Prerequisites
 Automata theory (CS208 or equivalent) and Discrete Structures (CS207 or equivalent).
Reference Material

Elementary Net Systems (PDF),
Grzegorz Rozenberg and Joost Engelfriet,
Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Springer LNCS 1491 (1998) 12121. 
Some Behavioural Aspects of Net Theory (PDF),
P.S. Thiagarajan,
Theoretical Computer Science, 71 (1990) 133153. 
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) 122173. 
Structure theory of Petri nets: the free choice hiatus (PDF),
E. Best,
Advances in Petri nets 198687, part 1 on Petri nets , Springer LNCS 254 168205. WellStructured Transition Systems Everywhere! (PDF),
Alain Finkel and Philippe Schnoebelen,
Theoretical Computer Science 256(12), pages 6392, 2001.Algorithmic Aspects of WQO Theory (PDF),
Sylvain Schmitz and Philippe Schnoebelen,
Lecture notes for MPRI Masters' course, France 2012.Automata on Distributed Alphabets (PDF,PDF 2in1)
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  Freechoice nets, extended freechoice nets and behavioural freechoice 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. Omegafiring 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  Wellstructured 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 upperbounds, statement of the length function theorem (Chapter 2 of reference F)  
Apr 05  More examples and results for upperbounds, reductions (Chapter 2 of reference F)  
Apr 08  A strategy for finding lowerbounds: examples and some results. (Chapter 3 of reference F)  
Apr 12  Other formal models for concurrency: products of automata ( reference G) 