Ph.D témakiírások

 

ELTE Informatikai Doktori Iskola

 

 

Témavezető:  Csuhaj Varjú Erzsébet

 

tudományos tanácsadó, az MTA doktora

MTA SZTAKI, 1111 Budapest, Kende utca 13-17.

 

E-mail:       csuhaj@sztaki.hu

Web: http://www.sztaki.hu/~csuhaj/

 

 

1. Kutatási téma:

 

Nyelvprocesszor-hálózatok tulajdonságai

 

 

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

 

 A kutatási cél masszívan párhuzamos működésű, nyelvprocesszorokból álló hálózatok mint számítási modellek tulajdonságainak vizsgálata.  A nyelvprocesszorok átíró rendszerek (pl. nyelvtanok), amelyek szavakat és szavakból álló multihalmazokat  dolgoznak  fel és közvetítenek egymásnak, különféle működési és kommunikációs protokolloknak megfelelően.

 

A kutatások az alábbi problémakörökre irányulhatnak:

 

1.         problémák megoldása igen nagyszámú csúcspontot tartalmazó nyelvprocesszor-hálózatok segítségével,

 

2.         algoritmusok, programnyelvek elméleti alapjainak kidolgozása ilyen hálózatokra,

 

3.         különböző típusú nyelvprocesszor-hálózatok méret-, kiszámítási- és kommunikációs bonyolultságának,

 

4.         valamint tér-idő dinamikájának (tér-időbeli minták kialakulása) vizsgálata,

 

5.         jelenségek (hullámjelenség, örvény) tanulmányozása a hálózatokban.

 

 

A várható eredmények hatékony, újszerű, osztott architektúrák elveinek kidolgozásában, számítógép hálózatokon működő, nagy létszámú közösségek viselkedésének leírásában (pl. mobiltelefon használók, Internet felhasználók), illetve természetes rendszerek (pl. biológiai vagy kémiai rendszerek) működésében használhatók.

 

A résztéma és a kutatási feladat pontos kijelölésére a jelentkezővel való egyeztetés után kerül sor.

 

Jelentkezési határidő: 2009. április 2 – május 31.

 

Irodalom:

 

1.     J. Castellanos, P. Leupold, V. Mitrana, On the size complexity of hybrid networks of evolutionary processors, Theoretical Computer Science 330(2) (2005) 205-220.

 

2.     J. Castellanos, C. Martín-Vide, V. Mitrana, J. Sempere, Solving NP-complete problems with networks of evolutionary processors. in: J. Mira, A. Prieto (Eds.), IWANN 2001,  Lecture Notes in Computer Science 2084, Springer, 2001, pp. 621-628.

 

3.     E. Csuhaj-Varjú,  Networks of language processors. EATCS Bulletin 63 (1997), 120-134.

 

4.     E. Csuhaj-Varjú, J. Dassow, J. Kelemen and Gh. Paun,  Grammar systems. A grammatical approach to distribution and  cooperation. Topics in Computer Mathematics 8.  Gordon and Breach Science Publishers, Yverdon, 1994.

 

5.     E. Csuhaj-Varjú, C. Martín-Vide, V. Mitrana, Hybrid networks of evolutionary processors are computationally complete.  Acta Informatica  41(4-5) (2005) 257-272.

 

6.     E. Csuhaj-Varjú, A. Salomaa, Networks of parallel language processors. In: Gh. Paun, A. Salomaa (Eds.), New Trends in Formal Languages, LNCS 1218, Springer Verlag, 1997, 299-318.

 

7.     J. Dassow, B. Truthe, On the Power of Networks of Evolutionary Processors, in: J. O. Durand-Lose, M. Margenstern (Eds.), MCU 2007, Lecture Notes in Computer Science 4667, Springer, 2007, pp. 158-169.

 

8.     J. Dassow, Gh. Paun, and G. Rozenberg,   Grammar systems. in: A. Salomaa and G. Rozenberg (Eds.), Handbook of Formal Languages, Volume 2, Chapter 4, Springer-Verlag,   Berlin-Heidelberg, 1997, pp. 155-213.   

 

9.     F. Manea, C. Martín-Vide, V. Mitrana, On the size complexity of universal accepting hybrid networks of evolutionary processors, Mathematical Structures in Computer Science 17(4) (2007) 753-771.

 

10. F. Manea, C. Martín-Vide, V. Mitrana,   All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary  processors of constant size, Information Processing Letters 103 (2007) 112-118.

 

11. M. Margenstern, V. Mitrana, M.-J. Pérez-Jiménez, Accepting Hybrid  Networks of Evolutionary Processors, in: C. Ferretti, G. Mauri, C. Zandron (Eds.), DNA 10, Lecture Notes in Computer Science 3384, Springer, 2005, pp. 235-246.

 

12. C. Martín-Vide, V. Mitrana, M.  Pérez-Jiménez, F. Sancho-Caparrini, Hybrid networks of evolutionary processors, in: E. Cantú-Paz et al. (Eds.), Proc. of  GECCO 2003, Lecture Notes in Computer Science 2723, Springer, 2003, 401–412.

 

 

 

2. Kutatási téma:

 

Membrán rendszerek

 

 

 

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

 

 

A kitűzött feladat kutatások végzése az  utóbbi években nemzetközi viszonylatokban intenzíven tanulmányozott membrán rendszerek vagy P rendszerek  területén. A membrán rendszerek az élő sejt felépítését követő és annak működését utánozó  osztott konstrukciók, amelyek ún. membránokkal határolt régiókból állnak, amely régiók objektumokat tartalmaznak. Az objektumok molekuláknak, kémiai alkotórészeknek felelnek meg. A rendszer működése során az objektumok változni (fejlődni) tudnak, valamint közlekedni képesek  a szomszédos régiók között, bizonyos szabályok szerint.  A P rendszerek  a régiók tartalmát, azaz, a bennük levő objektumok összességét szimbólumok vagy szavak  multihalmazaival jelenítik meg, a fejlődési, illetve a közlekedési szabályokat pedig formális nyelvi átírási szabályokkal írják le.

  A P rendszer fogalmát Gheorghe Paun vezette be 1998-ban, azóta az elmélet a molekuláris számítástudomány egyik, az érdeklődés homlokterében álló ágává fejlődött  (pl. az Institute for Scientific Information 2003. októberében ún. Fast Emerging Research Front in Computer Science” besorolásban részesítette).

 

A kutatások elsősorban az alábbi problémakörökre irányulhatnak:

 

1.       P automaták (környezetükkel interakcióban levő P rendszerek), azaz automata-szerű elfogadó P rendszerek vizsgálata  különös tekintettel a hagyományos, valamint az  újszerű, a hagyományosaktól eltérő típusú bonyolultsági mértékekre. A P automaták és a klasszikus automaták  tulajdonságainak összevetése.

 

2.       P rendszerek mint diszkrét dinamikus rendszerek vizsgálata

 

A várható eredmények hatékony, újszerű számítási paradigmák kialakításában alkalmazhatók, illetve alapjául szolgálhatnak további, a molekuláris biológiai jelenségek tanulmányozásához használatos szimulátorok kifejlesztéséhez.

 

 

 

 

A résztéma és a kutatási feladat pontos kijelölésére a jelentkezővel való egyeztetés után kerül sor.

 

Jelentkezési határidő: 2009. április 2 – május 31.

 

 

Irodalom:

 

1.     Gh. Paun: Membrane Computing. An  Introduction. Springer Verlag, Berlin-Heidelberg, 2002.

.

2.     G. Ciobanu, M.-J. Pérez-Jiménez and Gh. Paun ( eds.): Applications of Membrane Computing. Natural Computing Series, Springer, Berlin, 2006, 389-410.

 

3.     E. Csuhaj-Varjú: P automata.  In: G. Mauri, Gh. Paun, M.-J. Pérez-Jiménez, G. Rozenberg and A. Salomaa (eds.),  Membrane Computing: 5th International Workshop, WMC 2004, Milan, Italy, June, 14-16, 2004. Revised Selected and Invited Papers.  Lecture Notes in Computer Science 3365, Springer, 2005, 19-35.

 

4.     E. Csuhaj-Varjú, O.H. Ibarra and Gy. Vaszil: On the computational complexity of P automata. Natural Computing 5(2) (2006), 109-126.

 

5.     E. Csuhaj-Varjú and Gy. Vaszil: P automata or purely communicating accepting P systems. In: Gh. Paun, G.  Rozenberg, A. Salomaa and C. Zandron (eds.), Membrane Computing. International Worskhop, WMC-CdeA 2002, Curtea de Arges, Romania, August 19-23, 2002, Revised Papers. Lecture Notes in Computer Science 2597,Springer, Berlin, 2003, 219-233.

 

6.     E. Csuhaj-Varjú and Gy. Vaszil: (Mem)brane automata. Theoretical Computer Science 404(1-2) (2008), 52-60.

 

7.     J. Dassow and Gy. Vaszil:  P finite automata and regular languages over  countably infinite alphabets. In: H.-J. Hoogeboom, Gh. Paun, G. Rozenberg and A. Salomaa (eds.), Membrane Computing. 7th International Workshop, WMC 2006, Leiden, The Netherlands, July 17-21, 2006, Revised, Selected, and Invited Papers. Lecture  Notes in Computer Science 4361, Springer-Verlag, Berlin, 2006, 367-381.

 

További információkért lásd: http://ppage.psystem.eu