Bejelentkezés
 Fórum
 
 
Témakiírás
 
Fülöp Zoltán
Súlyozott faautomaták és fatranszformátorok

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
matematika- és számítástudományok
Matematika- és Számítástudományok Doktori Iskola

témavezető: Fülöp Zoltán
helyszín: SZTE TTIK Matematika- és Számítástudományok Doktori Iskola 6720 Szeged, Aradi vértanúk tere 1.
helyszín rövidítés: MatDI


A kutatási téma leírása:

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

Transducers. Monogr. Theoret. Comput. Sci. EATCS Ser. Springer-Verlag, 1998.

[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.

felvehető hallgatók száma: 1

Jelentkezési határidő: 2016-11-30

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 1.2318 ( 2016. XI. 26. )