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