Automaty na nieskończonych obiektach 2010/2011


5 października

Twierdzenie: Zbiory słów skończonych, które można zdefiniować w monadycznej logice drugiego rzędu (MSO), to dokładnie języki regularne. Na słowach nieskończonych automat działa jak zwykle, tylko żeby zaakceptować musi nieskończenie często przejść przez stan akceptujący (tzw. warunek Buchiego). Języki rozpoznawane przez takie automaty to tzw. języki omega-regularne. Twierdzenie: Zbiory niesłów skończonych, które można zdefiniować w MSO, to dokładnie języki omega-regularne. Dowód jak dla słów skończonych, ale wymaga wykazania, że języki omega-regularne są zamknięte na dopełnienie (patrz nastepny wykład). Materiały: 1. i 2. wykład ze skryptu Automaty a logika.
12 października

Ogólniejszy model automatów ma warunek Mullera zadany przez rodzinę podzbiorów przestrzeni stanów. Bieg jest akceptujący, o ile zbiór stanów pojawiających się nieskończenie często jest w tej rodzinie. Fakt: Każdy automat Mullera jest równoważny automatowi Buchiego. Twierdzenie (trudne): Każdy automat Buchiego jest równowazny deterministycznemu automatowi Mullera. Wniosek: Języki omega regularne są zamknięte na dopełnienie. Materiały: sekcje 2.2.1 i 2.3 z Automata: From Logics to Algorithms.
19 października, 26 października, 2 listopada, 9 listopada

Materiały są na stronie Henryka Michalewskiego.
16 listopada

Ciągłe redukcje i gry Wadge'a. Lemat Wadge'a. Twierdzenie (Martin, Monk): Redukcje Wadge'a nie pozwalają na nieskończone łańcuchy malejące. Modyfikacja gier Wadge'a, w której drugi gracz może opuszczać kolejkę. Drugi gracz ma strategie wygrywającą w W(A,B) wtw, gdy istnieje ciągła redukcja z A do B. Materiały: sekcja 21.E z książki Kechrisa, Wikipedia. Praca domowa jest tutaj. Trzeba ją oddać na papierze 30 listopada.
UWAGA: W zadaniu 4 należy założyć, że M>1 lub N>1.
23 listopada

Niech A[u] oznacza zbiór takich słów nieskończonych x, że ux jest w A. Twierdzenie: Zbiór borelowski A jest nierownoważny swojemu dopełnieniu wtw, gdy istnieje takie nieskończone słowo x, że dla każdego skończonego prefiksu u, A[u] jest w równoważne A. (Twierdzenie 13 w artykule J. Duparca Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank.) Wniosek: Na granicznych poziomach hierarchii Wadge'a są dwie nieporównywalne klasy równoważności (Por. Sekcja 2 i Fakt 6 z artykułu J. Duparca A hierarchy of deterministic context-free omega-languages).
30 listopada, 7 grudnia

Hierarchia Wagnera, czyli klasyfikacja jezykow regularnych w hierarchii Wadge'a. Gry na automatach, operacja zlozenia sekwencyjnego i alternatywy, automaty kanoniczne, scislosc hierarchii automatow kanonicznych, zamkniecie automatow kanonicznych na operacje zlozenia sekwencyjnego i alternatywy (modulo rownowaznosc Wadge'a), pelnosc hierarchii automatow kanonicznych (modulo rownowaznosc Wadge'a). Materialy: sekcje 3.1 - 3.5 z mojego doktoratu (tylko fragmenty dotyczace slow), rozdzial o hierarchii Wagnera z ksiazki D. Perrin i J.-E. Pina "Infinite words" (uwaga: dosc odmienna metodologia, moze zmylic).
14 grudnia

Pozycyjna determinacja gier parzystosci. Twierdzenie Rabina.

Druga praca domowa jest dostepna tutaj. Rozwiazania trzeba przeslac poczta elektroniczna na moj adres.
Na Panstwa prosbe, przedluzam termin rozwiazywania zadan: prosze je przeslac do konca sesji, tj. do 6 lutego.
21 grudnia, 4 stycznia, 11 stycznia, 18 stycznia

Materiały są na stronie Henryka Michalewskiego.
Wyniki z prac domowych
Filip Murlak 20-10-2010