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
- Discrete Structures, e.g., CS207 or equivalent (hard requirement, mandatory) and Automata theory (soft requirement, recommended but not mandatory)
Reference Material
-
Lecture Notes on Petri Nets (PDF),
Javier Esparza, 2019.
-
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. -
Some Behavioural Aspects of Net Theory (PDF),
P.S. Thiagarajan,
Theoretical Computer Science, 71 (1990) 133-153. -
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. -
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. Well-Structured Transition Systems Everywhere! (PDF),
Alain Finkel and Philippe Schnoebelen,
Theoretical Computer Science 256(1-2), pages 63-92, 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 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 | |
|---|---|---|
| Lec 01: Wk 01 | Introduction, course outline (PDF). | |
| Lec 02: Wk 02 | Petri nets, basic definitions, examples, dynamics of a net, token game, elementary net systems, place/transition nets. Dynamics as a transition system: the reachability graph. ( reference A, B and D) | |
| Lec 03: Wk 02 | Fundamental situations: Concurrency, Conflict, Causality, Contact, Confusion. Confusion-free subclasses of nets: S-systems, T-systems, free-choice nets. ( reference A, B and C) | |
| Lec 04: Wk 03 | Behavioral theory of ENS: firing sequences and Mazurkiewicz traces ( reference A and C) | |
| Lec 05: Wk 03 | Behaviour of net systems: posets, extending traces, compatibility and poset on traces, event structures ( Reference C) | |
| Lec 06: Wk 04 | Place/Transition (Petri) nets, basic definitions and properties, Problems for Petri nets: Boundedness, reachability, liveness, coverability problems. ( reference A) | |
| Lec 07: Wk 04 | Guest Lecture | |
| Lec 08: Wk 05 | Algorithms for Petri nets: (Non)-termination, boundedness, Dickson's Lemma, Omega-firing sequences. ( reference A) | |
| Lec 09: Wk 05 | Algorithms for Petri nets: Karp Miller Coverability trees and their finiteness, Decidability of coverability, extensions. ( reference A) | |
| Lec 10: Wk 06 | Quasi orders and well quasi orders, well-structured transition systems ( reference F and G) | |
| Lec 11: Wk 06 | Multiple definitions of wqos, different notions of Compatibility, Higman's lemma and its proof ( reference F and G) | |
| Lec 12: Wk 07 | Finite reachability tree construction for termination problem for WSTS, effectivity conditions. ( reference F and G) | |
| Lec 13: Wk 07 | Finite Basis of WQOs, Backward set saturation algorithm, decidability of coverability, application to Petri nets ( reference F , G and A ) | |
| Feb 15 | Quiz 1 | |
| Lec 14: Wk 08 | Applications of WSTS beyond Petri nets: Integral Programs and lossy channel systems ( reference F and G) | |
| Feb 23-29 | Midsem week | |
| Lec 15: Wk 09 | Automata over a distributed alphabet: Direct products and shuffle languages ( reference H) | |
| Lec 16: Wk 09 | Automata over a distributed alphabet: Synchronized Product automata and languages ( reference H) |