témavezető: Dömösi Pál Béla
helyszín (magyar oldal): Debreceni Egyetem Informatikai Kar helyszín rövidítés: DE IK
A kutatási téma leírása:
Szavak és nyelvek kombinatorikus tulajdonságai. Iterációs lemmák. Korlátos és palindromikus nyelvek. A primitív szavak nyelve. Kászonyi-Katsura elmélet. Eldönthetőség és bonyolultság. Automaták és nyelvek kapcsolata. Automaták és automata leképezések. Automaták kompozíciói és teljes rendszerei. Automata hálózatok mint automaták szorzatai. Krohn-Rhodes elmélet. A Leticsevszkij kritérium. Primitív szorzat és temporális szorzat. Állapot-homogén automata hálózatok. Aszinkron automata hálózatok.
Irodalom:
1. Dömösi Pál, Falucskai János, Horváth Géza, Mecsei Zoltán, Nagy Benedek: Formális nyelvek és automaták. TAMOP 4.2.5 Pályázat könyvei, Debrecen, 2011. http://www.tankonyvtar.hu/en/tartalom/tamop425/0046_formalis_nyelvek_es_automatak/adatok.html
2. Pál Dömösi and Masami Ito: Context-free languages and primitive words. World Scientific, NJ, London, Singapore, etc. 2015, ISBN 978-9814271660.
3. Dömösi, Pál; Nehaniv, Chrystopher, L.: Algebraic theory of automata networks. An introduction., SIAM, Philadelphia, 2005, ISBN 0-89871-569-5
4. J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation. 3rd ed., Pearson Education Ltd. London, 2014.
ajánlott nyelvtudás (magyar oldal): angol felvehető hallgatók száma: 1