Na seminarium dotkniemy rożnych aspektow dotyczących złożoności
deterministycznych i niedeterministycznych automatow skończonych.
Polegać to będzie na przeczytaniu i prezentacji kilkunastu wybranych artykułow
(oryginalnych lub przeglądowych), głownie z ostatnich lat.
Seminarium powinno być interesujące dla osob ktorym podobała się pierwsza
część wykładu z językow formalnych.
Przykładowe zagadnienia, ktore będą się pojawiać to
pytania o złożoność problemow rozpoznawania własności języka regularnego
akceptowanego przez automat,
algorytmy działające na automatach skończonych,
oszacowania wielkości minimalnego automatu rozpoznającego języki danego
rodzaju.
Sporo uwagi poświęcimy aktualnie otwartym problemom.
Parę prac przeglądowych:
\-- o złożoności opisowej i obliczeniowej automatow skończonych:
[[link](https://www.sciencedirect.com/science/article/pii/S0890540110001999)]
\-- o złożoności stanowej automatow skończonych:
[[link](http://arxiv.org/abs/1509.03254)]
\-- o niedeterministych automatach skończonych:
[[link](https://www.researchgate.net/publication/221568010)]
