témavezető: Gazdag Zsolt
helyszín (magyar oldal): University of Szeged helyszín rövidítés: SZTE
A kutatási téma leírása:
A membrán rendszerek (más néven P rendszerek) [2,4] az élő sejtek formális nyelvi modelljei. Egy ilyen rendszer membránok által határolt, hierarchikusan szervezett régiókból áll. A régiók objektumokat tartalmaznak, melyek a sejtekben lévő kémiai alkotóelemeknek felelnek meg. Ezen objektumok változhatnak és mozoghatnak is a régiók között a régiókhoz rendelt szabályok szerint. A membrán rendszerek egy sokat kutatott változata az aktív membrános P rendszerek [3]. Itt a membránok rendelkeznek egy polaritással, ami befolyásolhatja egy adott szabály alkalmazhatóságát. Megjelenik továbbá egy új szabály típus is, mellyel az elemi membránok kettéoszthatóak. Ismert, hogy ezek a rendszerek képesek NP-teljes problémák elméletileg hatékony megoldására.
Egy ígéretes kutatási téma annak vizsgálata, hogy milyen bonyolultságú problémák megoldására képesek az aktív membrános P rendszerek ha valamilyen módon megszorítjuk őket (például bizonyos típusú szabályok nem használhatóak [lásd pl. 1]). A témában számos nyitott kérdés van. Az egyik legismertebb a Paun-sejtés, miszerint ezek a rendszerek a membránok polaritása nélkül csak P-beli problémák megoldására képesek. A sejtés speciális esetekben való igazolása is egy sokat kutatott és számos további lehetőséget rejtő témakör.
Ezen kérdések megválaszolása segítheti a klasszikus számítási modellekkel kapcsolatos bonyolultság-elméleti kérdések jobb megértését is. A témára olyan hallgató jelentkezését várjuk, aki érdeklődik a klasszikus és új-elvű számítási modellek iránt és szívesen végezne kutatásokat a vázolt témában.
[1] Z. Gazdag and G. Kolonits. Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes. In: Proceedings of the 17th International Conference on Membrane Computing (Eds. A. Leporati and C. Zandron). CMC17, 137-160, 2016.
[2] Gh. Paun. Computing with membranes. J. Comput. Syst. 61(1):108-143, 2000.
[3] Gh. Paun. P Systems with Active Membranes: Attacking NP-Complete Problems. Journal of Automata, Languages and Combinatorics, 6(1): 75-90, 2001.
[4] Gh. Paun, G. Rozenberg, and A. Salomaa (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, England, 2010.
ajánlott nyelvtudás (magyar oldal): angol felvehető hallgatók száma: 1
Bejelentkezés
