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) 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. -
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) 257-308. -
Complexity Analysis of Continuous Petri Nets. (PDF),
EstÃbaliz Fraca, Serge Haddad,
Fundam. Inform. 137(1): 1-28 (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 20-23, 2017. IEEE Computer Society 2017. 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 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.-
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), 1-38, 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, free-choice 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, well-quasi orders and well-structured 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 anti-chain condition, downward closed sets, the Erdos-Tarski 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 upper-bounds, statement of the length function theorem (Chapter 2 of reference H) | |
| Mar 27 | More examples and results for upper-bounds, 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) |