24 kwietnia 2018 12:15
Jan Otop: Podejście ilościowe w teorii automatów i jego zastosowania
We wtorek 24 kwietnia o godz. 12.15 w sali 119 Instytutu Informatyki odbędzie się wykład przedhabilitacyjny dra Jana Otopa pt. ,,Podejście ilościowe w teorii automatów i jego zastosowania''
Serdecznie zapraszamy
Streszczenie:
W klasycznej teorii automatów dominuje podejście jakościowe --- automaty skończone akceptują bądź odrzucają słowa wejściowe i w efekcie każdy automat wyznacza zbiór słów akceptowanych, nazywany jego językiem. Jako że język jest zbiorem, podstawowe problemy w teorii automatów mają charakter teoriomnogościowy, tj. pytamy o należenie (danego słowa) do języka, pustość języka, czy zawieranie się języków. Takie pytania mają charakter jakościowy, ale okazuje się, że zarówno one jak i same automaty mają swoje odpowiedniki ilościowe.
W teorii automatów występują dwa trendy w badaniach łączących automaty oraz podejście ilościowe. W pierwszym, rozważane są rozszerzenia automatów o aspekty ilościowe takie jak czas, koszty, itp. W szczególności, automaty z wagami przyporządkowują słowom liczby i w efekcie każdy automat z wagami wyznacza funkcję ze słów w liczby. Teoriomnogościowe problemy dla automatów mają swoje funkcyjne odpowiedniki dla automatów z wagami. W drugim, pozostając przy klasycznych modelach automatów, rozważa się ilościowe uogólnienia klasycznych pytań. Np. zamiast należenia słowa do języka, rozważa się problem minimalnej odległości słowa od języka względem zadanej metryki na słowach.
W swoim wystąpieniu zaprezentuję wyniki dotyczące podejścia ilościowego w teorii automatów. W szczególności przedstawię:
1. Podstawowe pojęcia z teorii automatów.
2. Zastosowania teorii automatów. W szczególności, zastosowania podejścia ilościowego w teorii automatów.
3. Nowy model automatów ilościowych, nazywanych zagnieżdżonymi automatami z wagami.
4. Ilościowe problemy oraz analizę ilościową dla wprowadzonych
wcześniej modeli automatów.