Bejelentkezés
 Fórum
 
 
Témakiírás
 
Gazdag Zsolt
Az aktív membrános P rendszerek számítási bonyolultsága

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
informatikai tudományok
Informatika Doktori Iskola

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

Jelentkezési határidő: 2020-05-31

 
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ó: 2.2358 ( 2017. X. 31. )