Instructors
Tutors and tutorials
- Sergiy Bogomolov
Date, Time and Place
Monday, 15:00 c.t. - 17:00, SR 01-009, Geb. 101
Friday, 9:00 c.t. - 11:00, SR 00-010, Geb. 101
First lecture: 21.4.
Description
The theory of automata on finite strings, infinite strings and trees provides an expressive formal framework for reasoning about reactive systems, such as communication protocols and control systems. Reactive systems are characterized by their nonterminating behaviour and persistent interaction with their environment.
In this course we will discuss the following topics:
- Automata over infinite words and trees (omega-automata)
- Infinite two-player games
- Logical systems for the specification of nonterminating behavior
- Transformation of automata according to logical operations
Links & Literature
- Bakhadyr Khoussainov and Anil Nerode, Automata Theory and its Applications
- Automata, Logics, and Infinite Games: A Guide to Current Research by Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.) Lecture Notes in Computer Science 2500, Online Version [login from the University]
- Automata, Games and Verification, Lecture course by Prof. Dr. Bernd Finkbeiner [recommended to download his notes before the lectures: s1.pdf, s2.pdf, s3.pdf, s4.pdf, s5.pdf, s6.pdf, s7.pdf, s8.pdf, s9.pdf, s10.pdf, s11.pdf, s12.pdf, s13.pdf, s14.pdf, s15.pdf, s16.pdf]
Excercises
Mo 28.4., Fr 9.5., Mo 26.5., Fr 6.6, Fr 13.6, Mo 23.6
(further dates will be added, can be Monday as well as Friday);
Handouts
See also notes of Prof. Dr. Bernd Finkbeiner above.