Mikołaj Bojańczyk > Automaty a Logika (wykład 2013/2014) > Egzamin


Egzamin

Na ocenę dostateczną, wystarczy nauczyć się 5 wybranych tematów. Dalsze progi to: dobry = 8, bardzo dobry = wszystko. Termin należy umówić mejlem. Protokół z pierwszego terminu muszę zdać w środę 19 lutego, jest to więc ostatni dzień na egzamin (a mam wtedy 3 godziny wolne od zajęć, więc proponuję nie zwlekać do ostatniego dnia).

A. Słowa skończone

Udowodnij, że na słowach skończonych MSO=automaty

B. Słowa nieskończone

Zdefiniuj automat z warunkiem Büchiego i pokaż, że deterministyczne automaty z warunkiem Büchiego nie są równoważne niedeterministycznym

Pokaż, że niedeterministyczne automaty z warunkiem Büchiego są zamknięte na dopełnienie

Pokaż, że niedeterministyczne automaty z warunkiem Büchiego są równoważne deterministycznym automatom z warunkiem Mullera

C. Drzewa nieskończone i twierdzenie Rabina

Zdefiniuj gry z warunkiem parzystości i pokaż przykład gry (nie z warunkiem parzystości), która nie jest zdeterminowana

Udowodnij, że w grach z warunkiem parzystości, dla każdej pozycji jeden z graczy ma bezpamięciową strategię wygrywającą

Pokaż, że niedeterministyczne automaty z warunkiem parzystości są równoważne alternującym automatom z warunkiem parzystości

Pokaż, że dla alternujących automatów, więcej rang daje więcej siły wyrazu

Udowodnij, że słabe MSO jest równe automatom alternation-free

D. Pozostałe tematy

Zdefiniuj MSO-interpretację element-element i pokaż, że taka interpretacja zachowuje rozstrzygalność teorii MSO. Omów inne warianty interpretacji.

Zdefiniuj tree-width i pokaż, że dla każdego k rozstrzygalny jest problem, czy dane zdanie MSO jest prawdziwe w strukturze o tree-width k.

Udowodnij, że LTL = FO = półgrupy aperiodyczne

Udowodnij twierdzenie Simona