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. 
Basic Linear Algebraic Techniques for Place/Transition Nets (PDF),
Jörg Desel,
Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Springer LNCS 1491 (1998) 257308. 
Complexity Analysis of Continuous Petri Nets. (PDF),
EstÃbaliz Fraca, Serge Haddad,
Fundam. Inform. 137(1): 128 (2015)

Logics for continuous reachability in Petri nets and vector addition systems with states. (PDF),
Michael Blondin, Christoph Haase,
32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 2023, 2017. IEEE Computer Society 2017. 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 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.
The Theory of Message Sequence Charts (PDF),
K. Narayan Kumar,
In Deepak D'Souza and Priti Shankar (eds),
Modern Applications of Automata Theory, World Scientific. 
A Theory of Regular MSC Languages (PDF),
Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, Milind Sohoni and P. S. Thiagarajan
Information and Computation, vol 202(1), 138, 2005, Elsevier.
Topics covered
Date  Topics covered  

Jan 5  Introduction, course outline (PDF).  
Jan 9  No Class  
Jan 12  Basic definition of Petri nets, examples, dynamics, Token game, Elementary net systems, Place/transition nets, Fundamental situations: Concurrency, Conflict. ( reference A and B)  
Jan 16  Fundamental situations: Contact, Confusion; symmetric and asymmetric confusion. Subclasses of nets: sequential nets, marked graphs, freechoice nets. ( reference A and B)  
Jan 19  Behavior of net systems: firing sequences, traces, posets ( reference A and B)  
Jan 23  Behavior of net systems: processes, branching processes, unfoldings ( reference A and B)  
Jan 30  Quiz 1  
Feb 02  Place/Transition (Petri) nets, Problems: Termination, coverability, reachability, boundedness, liveness; Dickson's Lemma ( reference C)  
Feb 06  Place/Transition (Petri) nets: Coverability tree ( reference C)  
Feb 09  Guest lecture by Piotrek Hofman: Basic linear algebraic techniques and continuous reachability in Petri nets ( slides , reference E and F )  
Feb 13  Quasi orders, wellquasi orders and wellstructured transition systems ( reference G and H )  
Feb 16  Forward and backward algorithms for WSTS, Lossy channel systems ( reference G and H )  
Feb 20  Quiz 2  
Feb 23  Different compatibility relations, variants of Petri nets, Tutorial ( reference G)  
Feb 27  Midsem week  
Mar 02  Midsem week  
Mar 06  Guest lecture 1 by Alain Finkel: Finite antichain condition, downward closed sets, the ErdosTarski theorem and applications to verification of WSTS, WBTS ( slides 1 and slides 2)  
Mar 09  Guest lecture 2 by Alain Finkel: Exercises and revision, forward analysis for WSTS, repeated reachability, very WSTS ( exercise slides and very WSTS slides )  
Mar 13  Revision of algorithms on WSTS  
Mar 16  Complexity of WSTS: definitions, a new complexity hierarchy (Chapter 2 of reference H)  
Mar 20  Quiz 3  
Mar 23  Complexity of WSTS: finding upperbounds, statement of the length function theorem (Chapter 2 of reference H)  
Mar 27  More examples and results for upperbounds, reductions (Chapter 2 of reference H)  
Apr 03  Automata over distributed alphabet: direct products and shuffle languages ( reference I)  
Apr 06  Automata over distributed alphabet: Synchronized product and Asynchronous automata ( reference I) 