Mikołaj Bojańczyk > Automaty a Logika (wykład 2013/2014) > 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).
Udowodnij, że na słowach skończonych MSO=automaty
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
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
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