### Wymagania (prerequisites)
* Algorytmy i struktury danych
* Języki formalne i złożoność obliczeniowa
### Opis (description)
Seminarium poświęcone będzie algorytmom w teorii automatów. W ramach
seminarium prezentowane będę prace naukowe poświęcone temu tematowi. Niektóre
tematy będą klasyczne, inne stosunkowo świeże. Lista tematów (i prac) nie jest
wyczerpująca.
Zajęcia będą miały dwóch prowadzących - Artur Jeża oraz Pawła Gawrychowskiego.
### Program (program)
* minimalizacja automatów i jej warianty
* automaty pokrywające [ link ](http://springerlink.metapress.com/openurl.asp?genre=article{\\&}issn=0302-9743{\\&}volume=2608{\\&}spage=117)
* hiper-minimalizacja [link](http://dx.doi.org/10.1016/j.tcs.2010.05.029)
* k-minimalizacja
* równoważność automatów
* aproksymacja rozmiaru minimalnego automatu niedeterministycznego [ link ](http://portal.acm.org/citation.cfm?id=1268091)
* problem przynależności do języka Dycka, czyli poprawnych nawiasowań ([online](http://eccc.hpi-web.de/report/2009/119/) lub [ dynamicznie](http://portal.acm.org/citation.cfm?id=1036082))
* testowanie przynależności do języka regularnego w czasie podliniowym [link](http://www.computer.org/portal/web/csdl/doi/10.1109/SFFCS.1999.814641)
itp.
W zależności od oczekiwań uczestników, możemy skupić się na mocniej na
aspekcie klasycznym lub współczesnym.
