Stavová zložitosť automatov na vstupoch kódovaných homomorfizmami

Vedúci: RNDr. Zuzana Bednárová, PhD.
Pracovisko: ÚINF

Ciele práce

1. Oboznámiť sa a naštudovať súčasný stav problematiky v oblasti stavovej zložitosti automatov, minimalizácie, hyperminimalizácie a automatov s chybami.

2. Preskúmať súvis medzi stavovými zložitosťami jazykov a ich homomorfných kódov.

3. Navrhnúť metódy minimalizácie pre homomorfné kódy jazykov.

Zdroje

[1.] J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to automata theory, languages, and computation - international edition (2. ed). Addison-Wesley (2003);
[2.] A. Badr, V. Geffert, I. Shipman: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl. 43(1) (2009) 69-94
[3.] N. Moreira, G. Pighizzini, R. Reis: Optimal state reductions of automata with partially specified behaviors. In: Italiano G.F., Margaria-Steffen T., Pokorný J., Quisquater JJ., Wattenhofer R. (eds) SOFSEM 2015: Theory and Practice of Computer Science. SOFSEM 2015. Lecture Notes in Computer Science, vol 8939. Springer, Berlin, Heidelberg