Thesis supervisor: Zoltán Fülöp
Location of studies (in Hungarian): SZTE TTIK Matematika- és Számítástudományok Doktori Iskola 6720 Szeged, Aradi vértanúk tere 1. Abbreviation of location of studies: MatDI
Description of the research topic:
Közismert, hogy a ma már klasszikusnak mondható faautomaták és fatranszformátorok [6,8,9] általánosíthatók félgyűrük feletti ún. súlyozott faautomatákká és fatranszformátorokká. Az általánosítás során a fanyelv egy olyan leképezés lesz, amely a fák halmazát egy S félgyűrűbe képezi le. Ezáltal a félgyűrű elemei adják a fák súlyait. Az ilyen leképezéseket S feletti fasoroknak nevezzük. Hasonlóan, a fatranszformációnak egy olyan leképezés felel meg, amely a fákból S feletti fasorokba képez le. Mára mind a súlyozott faautomatáknak, mind a súlyozott fatranszformátoroknak komoly irodalma van, lásd a [5,7] összefoglalókat. Ugyanakkor aktív kutatás is folyik, melynek egyik fő fóruma a két évente megrendezésre kerülő Weighted Automata: Theory and Applications workshop sorozat.
Számos nyitott probléma és kutatásra alkalmas feladat maradt még ezen a területen. Ilyenek például a súlyozott fatranszformátorokra vonatkozó eldönthetőségi eredmények keresése, melyek alapjául a súlyozott faautomatákra vonatkozó [2] és [10] pozitív eldönthetőségi eredmények szolgálhatnak. Teljesen feldolgozatlan még a manapság intenzíven tanulmányozott fabejáró automaták [1,3,4] általánosítása súlyozott fabejáró automatákká.
A meghirdetett tématerv egy fő olyan hallgatónak szól, aki érdeklődik az elméleti számítástudomány iránt és szívesen végezne kutatómunkát ezen a területen.
Irodalom:
[1] A. V. Aho and J. D. Ullman, Translations on a context--free grammar, Inform. Control, 19 (1971) 439-475.
[2] S. Bozapalidis. Positive tree representations and applications to tree automata. Inform. and Control, 139(2):130--153, 1997.
[3] J. Engelfriet, H. J. Hoogeboom and J.-P. Van Best, Trips on Trees, Acta Cybernet., 14 (1999) 51-64.
[4] J. Engelfriet, G. Rozenberg and G. Slutzki, Tree transducers, {L} systems, and two--way machines, J. Comput. System Sci., 20 (1980) 150-202.
[5] Z. Ésik and W. Kuich. Formal tree series. J. Autom. Lang. Comb., 8(2):219--285, 2003.
[6] Z. Fülöp and H. Vogler. Syntax-directed semantics --- Formal Models Based on Tree
[7] Z. Fülöp and H. Vogler. Weighted Tree Automata and weighted Tree transducers. in: Handbook of Weighted Automata (Eds. M. Droste, W. Kuich, and H. Vogler). Springer-Verlag, 2009.
[8] F. Gécseg and M. Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984.
[9] F. Gécseg and M. Steinby. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, chapter 1, pages 1--68. Springer-Verlag, 1997.
[10] H. Seidl. Deciding equivalence of finite tree automata. SIAM J. Comput., 19(3):424--437, 1990.
Login
