---

Finite-State Dynamical Systems

Instructor:                         Kuize ZHANG (zhangkuize@gmail.com)

SSD:                                     ING-INF/04 – Automatic Control

Credits / hours:                2 credits / 20h

Language:                          English

Scheduling:                       June 10, 12, 14, 17, 19, 21, 24, 26, 28 (9.00-11.00 pm, room I, building I), and final exam in July (2h)

Final Exam:                       Written exam

Registration:                     Interested students should send an email to the instructor

Goal of the Course

The course contains basic knowledge on two classes of finite-state dynamical systems --- finite automata and weighted automata. For the former, basic tools --- concurrent composition and observer will be introduced, how to use them to verify basic inference-based properties and concealment-based properties in discrete-event systems modelled by finite automata will be introduced as well. For the latter, only basic definitions will be introduced and compared over semirings and monoids. Students will acquire basic knowledge in control theory and computer science based on these two classes of systems, and will also catch a glimpse of similarities and differences between them.

Prerequisites

The course is self-contained, so no prerequisites are needed. However, it would be better for the students to have preliminary knowledge on finite automata.

Intersection with other courses at the University of Cagliari: no significant intersections

Course Outline (2 hours per day)

Part 1: Finite automata

Day 1 (June 10): Alphabets, deterministic finite automata, and regular languages

Day 2 (June 12): Nondeterministic finite automata and powerset construction

Day 3 (June 14): Homework on finite automata and regular languages

Part 2: Finite automata in control

Day 4 (June 17): Labeled finite-state automata, concurrent composition, and detectability

Day 5 (June 19): observer, detectability enforcement based on concurrent composition

Day 6 (June 21): State-based opacity and its verification based on concurrent composition

Day 7 (June 24): Homework on finite automata in control

Part 3: Labeled weighted automata over semirings/monoids

Day 8 (June 26): Basic definitions in labeled weighted automata over semirings/monoids

Day 9 (June 28): Homework and tutorials

Day 10 (in July, to be determined): Final exam