lecture

tutorials

USOS

Lectures:

1. Introduction, elementary and general Petri nets, equivalent models, decision problems
   • W. Reisig, G. Rozenberg (ed.), Lectures on Petri Nets I: Basic Models, first two chapters:
     • J. Engelfriet, G. Rozenberg, Elementary Net Systems, sect. 3
     • J. Desel, W.Reisig, Place/Transition Petri Nets, sect. 1-3
   
   
2. Elementary nets: concurrency, dependence and conflict; confusions; regions - reconstruction from a finite automaton
   • J. Engelfriet, G. Rozenberg, Elementary Net Systems, rozdz. 3
   • J. Desel, W. Reisig, The synthesis problem of Petri nets, sect. 1-5
   
   
3. Mazurkiewicz traces, dependence graphs, regular trace languages, asynchronous automata, labeled elementary nets
   • A. Mazurkiewicz, Introduction to Trace Theory
   • V. Diekert, A. Muscholl, Construction of asynchronous automata, sect. 8.2
   
   
4. Coverability trees, universal lower bound for general nets
   • lecture notes
   • J. Desel, W.Reisig, Place/Transition Petri Nets, sect. 4
   • J. Esparza, Decidability and complexity of Petri net problems — an introduction, part II, sect. 7
   
   
5. The reachability problem - decidability
   • lecture notes
   • S. Lasota, VASS reachability in three steps
   • S. Kosaraju, Decidability of Reachability in vector addition systems
   
   
6. Approximate analysis: state equation, invariants, continuous reachability
   • lecture notes
   • J. Esparza, Free Choice Petri Nets, sect. 2
   • E. Fraca, S. Haddad, Complexity Analysis of Continuous Petri Nets
   
   
7. Confusion-less subclasses of Petri nets: P-nets, T-nets, free-choice nets
   • lecture notes
   • J. Esparza, Free Choice Petri Nets, sect. 3-4
   
   
8. The reachability problem - lower bound
   • lecture slides
   • S. Lasota, Improved Ackermannian lower bound for the Petri nets reachability problem
   • W. Czerwiński, Ł. Orlikowski, Reachability in Vector Addition Systems is Ackermann-complete
   
   
9. Process algebra CCS - syntax and semantics, examples
   • lecture notes
   • R. Milner, Communication and Concurrency, sect. 2,3
   • Notatki z wykładu Wybrane zagadnienia teorii procesów współbieżnych, sect. 2,3
   
   
10. Bisimulation equivalence
    • lecture notes
    • R. Milner, Communication and Concurrency, sect. 4
    • Lecture notes Wybrane zagadnienia teorii procesów współbieżnych, sect. 4
    
    
11. Observational equivalence
    • lecture notes
    • R. Milner, Communication and Concurrency, sect. 5, 7
    • Lecture notes Wybrane zagadnienia teorii procesów współbieżnych, sect. 5, 6
    
    
12. Bisimulation game, coinduction
    • lecture notes
    • R. Milner, Communication and Concurrency, sect. 4
    • Lecture notes Wybrane zagadnienia teorii procesów współbieżnych, sect. 4, 8
    
    
13. Bisimulation and logic
    • lecture notes
    • R. Milner, Communication and Concurrency, sect. 10
    • Lecture notes Wybrane zagadnienia teorii procesów współbieżnych, sect. 8
    • C. Stirling, Bisimulation and logic
    
    
14. Undecidability of bisimulation equivalence
    • lecture notes
    • Lecture notes Wybrane zagadnienia teorii procesów współbieżnych, sect. 7
    • Bergstra, J., Ponse, A., Smolka, S. (ed.), Handbook of Process Algebra, sect. 9
    • P. Jancar, Undecidability of bisimilarity for Petri nets and some related problems
    
    

Egzamin:

• zagadnienia