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