Teaching code

4S009002

Teacher

Tiziano Villa

Coordinatore

Tiziano Villa

Credits

9

Language

English

Scientific Disciplinary Sector (SSD)

ING-INF/05 - INFORMATION PROCESSING SYSTEMS

Period

Primo semestre dal Oct 4, 2021 al Jan 28, 2022.

Lessons timetable Moodle Seminars

Learning outcomes

The objective of the class is to describe formal methods to specify, analyze and synthesize discrete-event systems. Such systems encompass discrete heterogeneous and concurrent components at different levels of abstraction, and may be subject to real-time constraints and interact with continuous environments both natural and artificial. At the end the student will be able to demonstrate basic expertise about formalisms and algorithms to specify, analyze and synthesize discrete-event systems according to the paradigm of model-based design. This expertise will enable the student to: i) represent discrete-event systems by means of languages, finite-state automata and machines, Petri nets, hybrid automata; ii) analyze their behaviour by formal methods (structural and behavioural, exact and approximate); iii) synthesize supervisory controllers of plants described by finite automata with uncontrollable and unobservable events; iv) analyze the behaviour of simple hybrid systems with continuous and discrete dynamics. At the end of the class the student will be able to: i) evaluate autonomously advantages and disadvantages of different choices of specification formalisms, and of algorithms for the analysis and synthesis of discrete-event systems; ii) work together with application-domain specialists to choose the formal model suitable for the specification, analysis and control of a given system; iii) carry on independent study of formal methods for discrete-event systems both for industrial applications and scientific advancement.

Program

Introduction to systems theory: linear and non-linear systems,
combinational and reactive systems, causal and non-causal systems.
Discrete-event systems and state machines (finite and infinite).
Deterministic and non-deterministic finite state machines.
Composition of finite state machines.
Minimization, determinization. equivalente and containment checking of
finite state machines.
Simulation and bisimulation of finite state machines.
Finite-state controller synthesis with respect to safety and progress properties.

Models of Petri nets.
Reachability analysis of Petri nets: reachability and coverability graphs
and trees, state equations, incidence matrices.
Srtructural and behavioral properties of Petri nets.
Expressiveness of classes of Petri nets.

Supervisory control for regular automata and languages.
Existence and construction of a supervisor under partial controllability.
Existence and construction of a supervisor under partial observability.
Existence and construction of a non-blocking supervisor.
Over-approximating and under-approximatin solutions of the supervisor control prolem.

Hybrid automata: specification and behavior.
The reachibility problem for timed automata.

Bibliography

Examination Methods

The exam is a written test with theoretical questions and exercises.
The exams is passed with a score higher or equal to 18/30.

Teaching materials

•   AD-SISS-ch3_4 Specifica di macchine a stati finiti   (pdf, en, 519 KB, 25/11/21)
•   AD-TH Lezioni su sistemi e macchine a stati finiti (cartella di pdf)   (x-gzip, en, 3173 KB, 03/10/21)
•   DES-CL-ch1_4 Sistemi a eventi discreti e controllo supervisore   (x-gzip, en, 887 KB, 25/11/21)
•   RP-JC_p2 Sintesi logica da specifiche concorrenti   (pdf, en, 28440 KB, 25/11/21)
•   RP-MESS-ch2 Introduzione alle reti di Petri   (pdf, en, 294 KB, 25/11/21)
•   RP-TV1 Introduzione alle reti di Petri (Petri nets: introduction)   (pdf, it, 380 KB, 25/11/21)
•   RP-TV2 Reti di Petri: approfondimenti (Petri nets: advanced topics)   (pdf, it, 1312 KB, 25/11/21)
•   RP-TV4 Da sistemi di transizione a reti di Petri (From transition systems to Petri nets)   (pdf, it, 1220 KB, 25/11/21)
•   SI-PV-1 Gli automi ibridi: sintassi e semantica   (pdf, en, 622 KB, 16/01/22)
•   SI-SISS-ch6 Specifica di automi ibridi   (pdf, en, 4918 KB, 16/01/22)
•   SI-SISS-sett4 Composizione di macchine a stati finiti   (pdf, en, 1078 KB, 16/01/22)
•   SISS Errata Corrige Varaiya-Lee   (postscript, en, 1190 KB, 25/11/21)
•   SI-TV-2 Gli automi ibridi: raggiungibilita'   (pdf, it, 189 KB, 16/01/22)
•   Stuzzichino (Teaser)   (pdf, en, 3424 KB, 02/03/22)
•   X1-TV Complementi ed esercizi   (pdf, it, 167 KB, 14/10/21)
•   XX-TV Temi d'esame   (x-gzip, it, 7268 KB, 31/12/21)