Course detail

# Petri Nets

FIT-PESAcad. year: 2018/2019

Basic concepts of Petri nets and their use in modelling of discrete-event 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 net-related problems, the problem of an automatic synthesis of Petri nets, restrictions and extensions of P/T Petri nets, coloured Petri nets, hierarchical and object-oriented Petri nets, Petri net-based tools, applications of Petri nets.

Supervisor

Department

Learning outcomes of the course unit

The acquired knowledge and experience will allow the students to actively use Petri nets and the computer-aided 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.

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 computer-based systems.

Prerequisites

Basic knowledge of discrete mathematics concepts including graph theory and formal languages concepts, basic concepts of algorithmic complexity, and principles of computer modelling.

Co-requisites

Not applicable.

Recommended optional programme components

Not applicable.

Recommended or required reading

- Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8
- Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3-540-60943-1
- Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4

- Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8
- Jensen, K.: Coloured Petri Nets, Basic Concepts, Analysis Methods and Practical Use, Springer Verlag, 1993. ISBN: 3-540-60943-1
- Girault, C., Valk, R.: Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications, Springer Verlag, 2002. ISBN 3-540-41217-4
- Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4
- Desel, J., Reisig, W., Rozenberg, G.: Lectures on Concurrency and Petri Nets, Advances in Petri Nets, Lecture Notes in Computer Science, č. 3098, Springer Verlag, 2004. ISBN 3-540-22261-8

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

A mid-term exam evaluation and an evaluation of projects.

Language of instruction

Czech

Work placements

Not applicable.

Course curriculum

- 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.
- Contact-free 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, free-choice 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 net-related 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 object-oriented Petri nets, basic concepts of a hierarchical design, substitution and invocation, adding object-oriented features on top of Petri nets, PNtalk as a language based on object-oriented Petri nets.
- An application of C/E systems.
- An application of P/T Petri nets.
- An application of CPNS.
- An application of object-oriented Petri nets.

**Syllabus of lectures:**

**Syllabus - others, projects and individual work of students:**

Aims

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 net-based computer-aided tools in typical applications.

Specification of controlled education, way of implementation and compensation for absences

A written mid-term exam (29 points) and 3 projects (7, 7 and 6 points).

Classification of course in study plans

- Programme IT-MGR-2 Master's
branch MBI , any year of study, summer semester, 5 credits, elective

branch MPV , any year of study, summer semester, 5 credits, elective

branch MSK , any year of study, summer semester, 5 credits, elective

branch MBS , any year of study, summer semester, 5 credits, elective

branch MMM , any year of study, summer semester, 5 credits, compulsory

branch MGM , 2. year of study, summer semester, 5 credits, elective

branch MIS , 2. year of study, summer semester, 5 credits, compulsory-optional

branch MIN , 2. year of study, summer semester, 5 credits, compulsory

#### Type of course unit

Lecture

39 hours, optionally

Teacher / Lecturer

Syllabus

- 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.

- Contact-free 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, free-choice 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 net-related 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 object-oriented Petri nets, basic concepts of a hierarchical design, substitution and invocation, adding object-oriented features on top of Petri nets, PNtalk as a language based on object-oriented Petri nets.

Project

7 hours, compulsory

Teacher / Lecturer

Syllabus

- An application of C/E systems.
- An application of P/T Petri nets.
- An application of CPNS.