Course contents


Reference Material

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)