Topics in automata at UBA
- Course on Friday morning from 9:30 to 13:00 room 12
- Bibliography
- Presentation
- Course n° 1 : infinite words
(Notes of S. Blundi)
[PP04, chap 1]
- alphabet, infinite words,
[PP04, p. 7-8]
- rational sets
[PP04, p. 13-16]
- Büchi automata
[PP04, p. 16-29]
- Course n° 2 : deterministic automata and complementation
[PP04, chap 1]
(Notes of S. Blundi)
- Büchi automata for Union and Intersection of regular sets
- Deterministic Büchi automata
[PP04, p. 31-35]
- Complementation (direct proof/construction)
[PP04] and
[LW92] for Ramsey's theorem
- Course n° 3 : Muller automata
[PP04, chap 1]
(Notes of S. Blundi)
- Correction of exercices
- Questions regarding the construction for complementation
- Algorithmic issues [PP04, p. 27]
- Each regular contains an ultimately periodic word [PP04, p. 27]
- Muller automata
[PP04, p.35]
- Course n° 4 : Muller automata (continued)
[PP04, chap 1]
(Notes of S. Blundi)
- Muller automata are not more powerful
[PP04, Thm 7.1]
- Union and Intersection and complementation of regular sets
- Muller automata and deterministic Büchi automata
- Course n° 5 : Safra's construction (continued)
[PP04, p. 45-55]
- Course n° 6 : automata and logic (Notes)
- Equivalence between MSO and automata
- Course n° 7 : games (Notes)
- Games on graphs, play, strategies
- Accessibility games
- Büchi games
- Parity games
- Muller games
- Course n° 8 : alternating automata
- Exam 7th December at 10:00 in Aula 10