Content
The course covers automata theory and its connection to logic.
The following topics will be discussed:
-
(deterministic, non-deterministic, alternating) finite automata
-
regular expressions
-
(weak) monadic second-order logic
-
Presburger arithmetic
-
(alternating) Büchi automata
-
linear-time temporal logic
Schedule
| week |
date |
topics |
slides |
exercises |
solutions |
|---|
| 01 |
05.10 & 09.10 |
deterministic finite automata, closure properties |
pdf (1x1, 4x1) |
pdf |
|
| 02 |
12.10 & 23.10 |
non-determinism, epsilon transitions |
pdf (1x1, 4x1) |
pdf |
|
| 03 |
19.10 & 30.10 & 06.11 |
regular expressions, homomorphisms |
pdf (1x1, 4x1) |
|
|
| 04 |
09.11 & 13.11 |
minimization, weak monadic second-order logic |
|
|
|
| 05 |
16.11 & 20.11 |
weak monadic second-order logic, Myhill-Nerode relations |
|
|
|
| 06 |
23.11 & 27.11 |
weak monadic second-order logic |
|
|
|
| 07 |
30.11 & 04.12 |
Presburger arithmetic |
|
|
|
| 08 |
07.12 & 11.12 |
Büchi automata |
|
|
|
| 09 |
14.12 & 18.12 & 08.01 |
complementation, monadic second-order logic |
|
|
|
| 10 |
11.01 & 15.01 |
generalized Büchi automata, linear-time temporal logic |
|
|
|
| 11 |
18.01 & 22.01 |
alternating (Büchi) automata, LTL model checking |
|
|
|
| 12 |
25.01 |
1st exam |
|
|
|
|
22.02 |
2nd exam |
|
|
|
|
21.05 |
3rd exam |
|
|
|
Literature
Slides and solutions to selected exercises will be made available online.
Accompanying literature will be provided.