Title:  Petri Nets 

Code:  PES 

Ac.Year:  2011/2012 

Term:  Summer 

Curriculums:  

Language:  Czech 

Public info:  http://www.fit.vutbr.cz/study/courses/PES/public/ 

Private info:  http://www.fit.vutbr.cz/study/courses/PES/private/ 

Credits:  5 

Completion:  examination (written&verbal) 

Type of instruction:  Hour/sem  Lectures  Sem. Exercises  Lab. exercises  Comp. exercises  Other 

Hours:  39  0  0  6  7 

 Examination  Tests  Exercises  Laboratories  Other 

Points:  51  29  20  0  0 



Guarantee:  Češka Milan, prof. RNDr., CSc., DITS 

Lecturer:  Češka Milan, prof. RNDr., CSc., DITS 
Instructor:  Rogalewicz Adam, doc. Mgr., Ph.D., DITS 

Faculty:  Faculty of Information Technology BUT 

Department:  Department of Intelligent Systems FIT BUT 

Prerequisites:  

Substitute for:  

 Learning objectives: 

  To acquire the basic concepts and methods of the theory of Petri nets and its applications in system modelling, design, and verification. To be able to practically use Petri netbased computeraided tools in typical applications.
 Description: 

  Basic concepts of Petri nets and their use in modelling of discreteevent systems, classification of Petri nets, the theory of C/E Petri nets, methods of analysis of C/E Petri nets, the theory of P/T Petri nets, methods of analysis of P/T Petri nets, Petri net languages, computability and complexity of Petri netrelated problems, the problem of an automatic synthesis of Petri nets, restrictions and extensions of P/T Petri nets, coloured Petri nets, hierarchical and objectoriented Petri nets, Petri netbased tools, applications of Petri nets.
 Knowledge and skills required for the course: 

  Basic knowledge of discrete mathematics concepts including graph theory and formal languages concepts, basic concepts of algorithmic complexity, and principles of computer modelling.  Subject specific learning outcomes and competences: 

  The acquired knowledge and experience will allow the students to actively use Petri nets and the computeraided tools based on them in modelling, design, verification, and implementation of various classes of systems. Based on the acquired theoretical knowledge, the student is able to transfer approaches of the Petri net theory to the domain of other formal models too.
 Generic learning outcomes and competences: 

  Abilities to apply and develop advanced information technologies based on suitable formal models, to propose and use such models and theories for automating the design, implementation, and verification of computerbased systems.
 Syllabus of lectures: 


 An introduction to Petri nets, their philosophy and applications, the notion of a net and of the derived basic terms
 Condition/Event (C/E) Petri nets, cases and steps, the state space of C/E systems, cyclic and live C/E systems, equivalence of C/E systems.
 Contactfree C/E systems, complementation, case graphs and their application for analysing C/E systems.
 Processes of C/E systems, occurrence nets, properties of properties and composition of processes.
 Complementation of C/E systems, the synchronic distance, special synchronic distances, C/E systems and the propositional calculus, facts.
 Place/Transition (P/T) Petri nets, their definition, evolution rules, their state space, basic analytical problems (safety, boundedness, conservativeness, liveness).
 Representing the possibly infinite state space of Petri nets by a reachability tree, computing and using reachability trees for analysing P/T Petri nets.
 P and T invariants of P/T Petri nets, their definition, the ways of computing them and using them for analysing P/T Petri nets.
 Subclasses and extensions of P/T Petri nets, state machines, marked graphs, freechoice Petri nets, Petri nets with inhibitors, timed and stochastic Petri nets.
 The notion of a Petri net language, types of such languages, their closure properties, their relation to the Chomsky hierarchy. Computability and complexity of some selected Petri netrelated problems.
 Coloured Petri nets (CPNs), their basic modelling primitives, an inscription language, CPN Design as an example of a tool based on CPNs.
 Analysis of CPNs, occurrence graphs, invariants, and their use in analysing systems.
 Hierarchical and objectoriented Petri nets, basic concepts of a hierarchical design, substitution and invocation, adding objectoriented features on top of Petri nets, PNtalk as a language based on objectoriented Petri nets.
 Syllabus  others, projects and individual work of students: 


 An application of C/E systems.
 An application of P/T Petri nets.
 An application of CPNS.
 An application of objectoriented Petri nets.
Each project implies modelling of a nontrivial system (or its part) by means of a Petri net of the given class and its simulation, analysis, and verification. Suitable computeraided tools (e.g., PESIM, INA, PEP, TimeNET, CPN Design, Maria, PNtalk, etc.) will be used in the projects.
 Fundamental literature: 


 Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0387137238
 Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3540609431
 Girault, C., Valk, R.: Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications, Springer Verlag, 2002. ISBN 3540412174
 Desel, J., Reisig, W., Rozenberg, G.: Lectures on Concurrency and Petri Nets, Advances in Petri Nets, Lecture Notes in Computer Science, vol. 3098, Springer Verlag, 2004. ISBN 3540222618
 Study literature: 


 Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0387137238
 Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3540609431
 Controlled instruction: 

  A written midterm exam, a regular evaluation of projects.  Progress assessment: 

  A midterm exam evaluation and an evaluation of projects.  
