Języki, automaty i obliczenia 1000-2D23JAO

Omawiamy wyniki związane z automatami skończonych wzbogaconymi o różne struktury (stos, liczniki, dane pochodzące z nieskończonego alfabetu, taśmy itd.), czyli innymi słowy z modelami obliczeń. Automaty mogą operować na słowach skończonych, nieskończonych, drzewach, a nawet grafach. Czasem po prostu akceptują daną strukturę (słowo / drzewo / inne), a czasem zwracają liczbę lub inną strukturę. Interesujemy się również zastosowaniami teorii automatów do innych dziedzin, typowym przykładem jest tu logika. Wiele twierdzeń dotyczących logiki opiera się na eleganckich technikach pochodzących z teorii automatów. Inny przykład to gry nieskończone, który w naturalny sposób często pojawiają się przy badaniu automatów. Teoria automatów wiąże się również ze złożonością obliczeniową, bo maszyna Turinga to przecież automat dwukierunkowy z nieskończoną taśmą. Na naszym seminarium czasem pojawiają się również inny ciekawe zagadnienia z informatyki teoretycznej, nawet jeśli nie są bezpośrednio związane z teorią automatów, logiką, ani z obliczeniami maszyn Turinga.

Na seminarium studenci referują polecone przez prowadzących tematy. Zazwyczaj polega to na przeczytaniu wskazanej pracy z czasopisma lub sprawozdania z konferencji poświęconych tej dziedzinie informatyki oraz przygotowaniu slajdów pod opieką jednego z prowadzących.