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.

Pokazać, że deterministyczne automaty Buchiego nie rozpoznają wszystkich języków omega-regularnych.
Pokazać, że każda formuła MSO jest równoważna formule z jednym kwantyfikatorem egzystencjalnym: "Istnieje zbiór X spełniający własność W(X)", gdzie W jest formułą logiki pierwszego rzędu.

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.

Udowodnij, rownoważność automatów Mullera i automatów Buchiego.
Pokaż, że każdy deterministyczny automat Mullera jest równoważny pewnemu deterministycznemu automatowi z warunkiem parzystości.
Wywnioskuj, że automaty z warunkiem parzystości są równoważne automatom Mullera i automatom Buchiego.

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.

Flipset nie jest zdeterminowany, więc nie jest borelowski.
Hierarchia indeksu dla deterministycznych automatów na słowach nieskończonych jest ścisła.
Każdy regularny język słów nieskończonych jest kombinacją boole'owską zbiorów typu Sigma_2.
Zbiór pusty i pełny są elementami minimalnymi względem redukcji Wadge'a. Bezpośrednio nad nimi leżą nietrywialne zbiory domknięto otwarte.

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).

Bezpośrednio powyżej każdego poziomu zawierającego dwie nieporównywalne klasy abstrakcji (poziom niesamodualny), jest poziom o jednej tylko klasie abstrakcji (poziom samodualny).
Bezpośrednio powyżej poziomu samodualnego jest poziom niesamodualny.
Podać (efektywne) kryterium na to, kiedy dany deterministyczny automat parzystości posiada równoważny automat deterministyczny o indeksie (1,2).

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