Języki, automaty i obliczenia II

• Automaty na słowach nieskończonych, algorytm determinizacji.

• Gry nieskończone, determinacja skończenie-pamięciowa.

• Automaty a głębokość gwiazdkowa wyrażeń regularnych.

• Automaty na drzewach skończonych i nieskończonych.

• Rozstrzygalność monadycznej logiki drugiego rzędu na drzewach nieskończonych.

• Algorytmy na grafach o ograniczonej szerokości drzewiastej.

• Automaty modelujące obliczenia współbieżne: sieci Petriego.

• Maszyny stratne: rozstrzygalność przy użyciu dobrych quasi-porządków (ang. wqo).

• Automaty uwzględniające upływ czasu: automaty czasowe.

• Automaty probabilistyczne/ważone: rozstrzygalność problemu równoważności.

• Automaty wielomianowe: rozstrzygalność problemu równoważności przy użyciu twierdzenia Hilberta o bazie.

• Algorytm uczenia automatów skończonych.

• Funkcje obliczalne przez automaty skończone.

• Przykłady zaskakująco prostych problemów nierozstrzygalnych. Stopnie nierozstrzygalności.

Wiedza

Student pogłębia wiedzę o klasycznych zagadnieniach obliczalności i poznaje kilka gałęzi współczesnej zaawansowanej teorii automatów.

Umiejętności

Student potrafi przechodzić pomiędzy różnymi reprezentacjami języków regularnych ze świadomością ograniczeń złożonościowych.

Student potrafi modelować proste własności systemów informatycznych za pomocą automatów, dobierając odpowiedni typ i mechanizm kontroli.

Student nabywa wprawy w rozpoznawaniu problemów nierozstrzygalnych i potrafi konstruować odpowiednie redukcje.

Kompetencje

Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii automatów i potrafi z nich korzystać zarówno w samej informatyce, jak i w jej zastosowaniach