témavezető: Nagy Benedek
helyszín (magyar oldal): Debreceni Egyetem Informatikai Kar helyszín rövidítés: DE IK
A kutatási téma leírása:
A klasszikus formális nyelvek és automaták elmélete az elméleti számítástudomány alapjai, egyes főbb definíciók és eredmények már 50-60 évesek. Azonban még a jól ismert nyelvosztályokkal, mint a reguláris, lineáris, vagy környezet-föggetlen nyelvosztályok, kapcsolatban is vannak érdekes nyílt problémák, illetve újabb kutatási irányok (pl. unió-normál forma a reguláris nyelvekhez, vagy speciális 2-fejű automaták a lineáris nyelvekhez). Vannak azonban jóval újabb automata modellek is (pl. átlátszóbetűs automaták), illetve nyelvtanok és egyéb formális modellek, amelyek segítségével új és érdekes nyelvosztályok definiálhatók. Ezen új nyelvosztályok különböző alkalmazások szempontjából lehetnek érdekesek.
Irodalom:
Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, 3 kötet, Springer, Heidelberg (1997)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, Reading MA, 1979.
Dömösi Pál, Falucskai János, Horváth Géza, Mecsei Zoltán, Nagy Benedek: Formális Nyelvek és Automaták, egyetemi jegyzet (Kelet-magyarországi Informatika Tananyag Tárház), 2011.
Herendi Tamás, Nagy Benedek: Párhuzamos algoritmusmodellek, Typotex, 2014.
ajánlott nyelvtudás (magyar oldal): angol felvehető hallgatók száma: 1