Automaty nieskończone 1000-2M22AN
Nieskończoność przestrzeni stanów jest wszechobecna w informatyce teoretycznej, prowadzi do niej np. nieograniczona głębokość stosu czy nieograniczona współbieżność. Często lepiej rozważać zbiór stanów, który jest nieskończony, niż sztucznie go ograniczać do zbioru skończonego ale astronomicznie wielkiego. Tak jest w m.in. przypadku automatów ze stosem, automatów rejestrowych, automatów czasowych czy sieci Petriego. Mimo nieskończonej przestrzeni stanów, istnieją tu algorytmy rozstrzygające istotne problemy decyzyjne, takie jak osiągalność albo równoważność. Przyjrzymy się najciekawszym problemom w tej dziedzinie, w szczególności rozstrzygalności osiągalności w sieciach Petriego. Wspomnimy też o ciekawych problemach, które pozostają wciąż otwarte.
Opowiemy o tematach wybranych spośród:
1. Zbiory semiliniowe, ich własności i zastosowania
2. Techniki oparte o wqo
3. Problemy decyzyjne dla 1-wymiarowych VASS
4. Stratne automaty licznikowe
5. Pokrywalność i osiągalność w VASS
6. Systemy odwracalne
7. Równoważności w systemach nieskończonych
8. Równoważność językowa deterministycznych automatów ze stosem
9. Separowalność w systemach nieskończonych
10. Automaty z rejestrami lub z zegarami
Kierunek podstawowy MISMaP
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Założenia (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza
Student pogłębia wiedzę o klasycznych zastosowaniach teorii automatów.
Umiejętności
Student umie rozpoznać granice obliczalności różnych wariantów modeli.
Student potrafi modelować różne problemy za pomocą odpowiednich automatów.
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
Kryteria oceniania
Zadania gwiazdkowe i egzamin ustny.
W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie rozwiązanie przynajmniej jednego zadania z gwiazdką bądź zapoznanie się z oryginalnym, będącym blisko aktualnego frontu badań, artykułem naukowym i rozmowa z wykładowcą na temat tego artykułu.
Literatura
Świeża literatura naukowa. W szczególności:
J. Fearnley, M. Jurdziński, Reachability in two-clock timed automata is PSPACE-complete, ICALP 2013.
Petr Jancar, Bisimulation Equivalence of 1st Order Grammars, ICALP 2014.
Roadmap of infinite results, http://www.brics.dk/~srba/roadmap/roadmap.pdf
S. Lasota, I. Walukiewicz, Alternating Timed Automata. ACM Transactions on Computational Logic 9(2), 2008.
W. Czerwiński, Ł. Orlikowski, Reachability in Vector Addition Systems is Ackermann-complete, FOCS 2021.
S.Lasota, VASS reachability in three steps, 2020.
Jan A. Bergstra, Alban Ponse, and Scott A. Smolka, ed., Handbook of Process Algebra, Elsevier, 2001.
W. Czerwinski, S. Lasota, R. Meyer, S. Muskalla, K. N. Kumar, P. Saivasan:
Regular Separability of Well-Structured Transition Systems. CONCUR 2018
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: