(in Polish) Języki, automaty i obliczenia

Tematem seminarium jest szeroko rozumiana teoria automatów.

Omawiamy ciekawe wyniki dotyczące zarówno klasycznej teorii automatów, jak i związanych z nią tematów, czyli: logiki, algorytmicznej teorii gier, teorii obliczeń, a czasem teorii złożoności i innych działów informatyki teoretycznej. Staramy się żeby przedstawiane konstrukcje były interesujące z matematycznego punktu widzenia i żeby były w miarę możliwości związane z zainteresowaniami naukowymi prowadzących. W związku z tym w aktualnej chwili najwięcej referatów dotyczy automatów ze stosem lub licznikami, automatów ważonych oraz gier nieskończonych, przy czym tematyka jest zdecydowanie szersza.

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.