Természet-motivált számítási modellek a formális nyelvek és automaták elméletében
Title in English
Nature-motivated computational models in the theory of formal languages and automata
Keywords in Hungarian
természet-motivált számítástudomány, membrán rendszerek, nyelvprocesszor hálózatok, formális nyelvek
Keywords in English
nature-motivated computation, membrane systems, networks of language processors, formal languages
Discipline
Computing Science (Council of Physical Sciences)
100 %
Panel
Mathematics and Computing Science
Department or equivalent
HUN-REN Institute for Computer Science and Control
Participants
Vaszil, György
Starting date
2008-10-01
Closing date
2012-10-31
Funding (in million HUF)
3.527
FTE (full time equivalent)
3.20
state
closed project
Summary in Hungarian
Kutatásaink a formális nyelvek és automaták elméletének eszközein alapuló osztott, természet-motivált számítási modellek vizsgálatára, valamint új konstrukciók kialakítására irányulnak.
A celluláris számítások elméletében kutatásaink súlypontját a membrán automatákra (P automatákra) helyezzük, amely konstrukciók mind a hagyományos automaták, mind a környezetükkel interakcióban lévő természetes osztott architektúrák sajátosságait hordozó eszközök. Vizsgálni tervezzük különböző változataik számítási erejét, robosztusságát, bonyolultsági jegyeit, az interakció hatását a környezet és a membrán rendszer viselkedésére, illetve ki szeretnénk alakítani az „absztrakt P automata családok” elméletét és egy, a P automatákra vonatkozó kalkulust és taxonómiát. Eredményeink hozzájárulhatnak az automata fogalmának jobb megértéséhez, a „természetes” automata fogalmának létrehozásához.
Tanulmányozni kívánjuk továbbá formális nyelvi műveleteken alapuló elemi számítási processzorok (biológiai indíttatású nyelvprocesszorok) hálózatainak tulajdonságait. A műveletek egyszerűsége miatt ezek a hálózatok kiváló példáját nyújtják a korlátozott sztring manipulációs lehetőségekkel bíró eszközöknek, azaz számítási erejük és méretbonyolultságuk tanulmányozása mellett lehetőség nyílik az általuk használt egyszerű műveletek korlátainak, az eldönthetőség határainak feltérképezésére is.
Várható eredményeink új eszközökkel gazdagítják az elméleti számítástudományt, hozzájárulnak a formális nyelvek és automaták elméletének továbbfejlesztéséhez, továbbá elvezethetnek a természetes folyamatok alapelveinek jobb megértéséhez is, így nemzetközi érdeklődésre tarthatnak számot.
Summary
We intend to construct and develop nature-motivated computational models and study their properties. The research, which enriches the theory of formal languages and automata, also can lead to a better understanding of the theoretical principles, the driving forces behind natural processes.
In the area of cellular computing, we focus our research on the so-called P automata which combine the features of traditional automata and nature-motivated distributed architectures. We intend to study the effect of their architecture and the way of the organization of their functioning elements on the computing power, the descriptional complexity, the robustness and on the dynamical patterns of their behavior. We plan to develop a theory of ``abstract families of P automata'', to establish a ``calculus'' and a taxonomy of these systems which might contribute to the development of the concept of a ``natural'' automaton.
In the area of networks of bio-inspired language processors, we plan to investigate the properties of networks of elementary processors based on simple formal language theoretic operations motivated by properties of DNA molecules. We are interested in these systems as examples of computational devices with very restricted string manipulating capability. Thus, our main goals include not only the study of their power and size complexity, but also the exploration of the ``limits'' of these language theoretic operations.
Our results are expected to be of interest for the international scientific community since they could extend our knowledge about some existing theoretical constructions, and provide us with more insight into current areas of interest both in nature-motivated computing and in the theory of formal languages and automata.
