Automaty nieskończone
Informacje ogólne
Kod przedmiotu: | 1000-2M22AN |
Kod Erasmus / ISCED: |
11.3
|
Nazwa przedmiotu: | Automaty nieskończone |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | angielski |
Kierunek podstawowy MISMaP: | informatyka |
Rodzaj przedmiotu: | monograficzne |
Wymagania (lista przedmiotów): | Języki, automaty i obliczenia 1000-214bJAO |
Założenia (lista przedmiotów): | Złożoność obliczeniowa 1000-218bZO |
Skrócony opis: |
Algorytmiczna analiza automatów o nieskończenie wielu stanach: automaty ze stosem, sieci Petriego, automaty nad alfabetem nieskończonym. |
Pełny opis: |
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 dwóm trudnym dowodom: rozstrzygalności osiągalności w sieciach Petriego i równoważności deterministycznych automatów ze stosem. Wspomnimy też o ciekawych problemach, które pozostają wciąż otwarte. Program: 1. Wprowadzenie: modele o nieskończenie wielu stanach, problemy decyzyjne, motywacja, granice rozstrzygalności 2. Niepustość ograniczonych automatów z licznikami 3. Osiągalność dla Sieci Petriego = VASS (ang. vector addition systems with states) 4. Ograniczoność dla VASS ze stosem 5. Osiągalność dla odwracalnych VASS ze stosem: siła zbiorów semiliniowych 6. Nieskończone alfabety: automaty z rejestrami, automaty alternujące 7. Równoważność językowa deterministycznych automatów ze stosem 8. Systemy jednoznaczne i problem wielorównoważności 9. Separowalność przez języki regularne |
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 |
Efekty uczenia się: |
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 |
Metody i 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. |
Zajęcia w cyklu "Semestr zimowy 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2024-10-01 - 2025-01-26 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Wojciech Czerwiński, Sławomir Lasota | |
Prowadzący grup: | Wojciech Czerwiński, Sławomir Lasota | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.