Természet-motivált számítási modellek a formális nyelvek és automaták elméletében  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
75952
típus K
Vezető kutató Csuhaj Varjú Erzsébet
magyar cím Természet-motivált számítási modellek a formális nyelvek és automaták elméletében
Angol cím Nature-motivated computational models in the theory of formal languages and automata
magyar kulcsszavak természet-motivált számítástudomány, membrán rendszerek, nyelvprocesszor hálózatok, formális nyelvek
angol kulcsszavak nature-motivated computation, membrane systems, networks of language processors, formal languages
megadott besorolás
Számítástudomány (Műszaki és Természettudományok Kollégiuma)100 %
zsűri Matematika–Számítástudomány
Kutatóhely Algoritmusok és Alkalmazásaik Tanszék (Eötvös Loránd Tudományegyetem)
résztvevők Vaszil György
projekt kezdete 2008-10-01
projekt vége 2014-09-30
aktuális összeg (MFt) 2.993
FTE (kutatóév egyenérték) 4.00
állapot lezárult projekt
magyar összefoglaló
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.
angol összefoglaló
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.




 

Zárójelentés

  
kutatási eredmények (magyarul)
Leírását adtuk a nem-determinisztikus Turing gépekkel logaritmikus tárban kiszámítható nyelvosztály egy, a természetes számítások szempontjából fontos valódi részosztályának P automaták (membrán automaták) egy valódi részosztályával. Kiterjesztve a számlálós gépek és osztott rendszereik fogalmát, megmutattuk, hogy a P automaták és osztott rendszereik (dP automaták) fontos részosztályai hogyan feleltethetők meg számlálós gépek változatainak. Leírását adtuk a nem-determinisztikus többfejű egy-, illetve kétirányú véges automaták által elfogadott nyelvosztálynak ún. véges dP automaták segítségével. Megmutattuk, hogy az ún. minimális interakcióval működő P rendszerek legtöbb változata, még korlátozott méretparaméterek esetében is a nem-negatív egészek rekurzíven felsorolható halmazainak osztályát határozza meg, és meghatároztuk olyan funkcionális blokkjait ezen rendszereknek, amelyek viselkedési mintáknak felelnek meg. Megmutattuk, hogy a legelemibb formális nyelvi műveletekkel (szimbólum cseréje, beszúrása, törlése) működő egyszerű, szövetszerű, környezetbe ágyazott P rendszerek automata változatai, az ún. P kolónia automaták működési módtól és a komponensek környezetétől függően a reguláris nyelvosztálytól a rekurzíven felsorolható nyelvosztályig terjedő kifejező erővel rendelkeznek. Bevezettük a topológiával kontrollált P rendszer fogalmát és összefüggést mutattunk meg egy kémiai kalkulus és a P rendszerek között.
kutatási eredmények (angolul)
We described a proper subclass of the class of languages computed by non-deterministic Turing machines in logarithmic space in terms of P automata. This language class is of special importance for natural computing. Extending the notion of counter machines and their distributed systems, we demonstrated how important variants of P and distributed P automata (dP automata) correspond to these tools. We presented a description of language classes of non-deterministic multihead one-way and two-way finite automata in terms of language classes of finite dP automata. We proved that most of the variants of P systems with minimal interactions detemine the class of recursively enumerable sets of non-negative intgers, even with limited size. We identified functional blocks in these systems that represent behavioural patterns. We showed that automaton-like variants of very simple tissue-like P systems working with elementary formal-language-theoretic operations (replacement, insertion, deletion of a symbol) and being embedded in an environment, called P colony automata, depending on their working mode and the presentation of their environment determine language classes from the regular to the recursively enumerable language class. We introduced the notion of a P system controlled by topology and established a connection between a chemical calculus and membrane systems.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=75952
döntés eredménye
igen





 

Közleményjegyzék

  
Csuhaj-Varjú, E: P Automata: Concepts, Results and New Aspects, pp. 1-16 in Paun, Gh et al. Proc. 10th Workshop on Membrane Computing, WMC10, RGNC Report 3/2009, Universidad de Sevilla, 2009
Csuhaj-Varjú, E: P Automata: Concepts, Results, and New Aspects, pp. 1-15 in Paun, Gh et al. Membrane Computing, 10th Int. Workshop, WMC 2009, LNCS 5957, Springer, 2010
Csuhaj-Varjú, E; Vaszil, Gy,: A Connection Between Finite dP Automata and Multi-head Finite Automata, pp. 109-126 in Gheorghe, M et al. Proc. Twelfth International Conference on Membrane Computing, Fontainebleau, Univ. of Paris Est Créteil Val de Marne, 2011
Cienciala, L; Ciencialová, L; Csuhaj-Varjú, E; Vaszil, Gy: PCol Automata: recognizing Strings with P Colonies, pp. 65-76 in Martínez-del-Amor, M.Á. et al. Proc. Eighth Brainstorming Week on Membrane Computing, Sevilla, 2010, Fénix Editora, Sevilla, 2010
Csuhaj-Varjú, E; Verlan, S: On generalized communicating P systems with minimal interaction rules, Theoretical Computer Science 412(1-2): 124-135, 2011
Csuhaj-Varjú, E; Vaszil, Gy; Verlan, S: On Generalized Communicating P Systems with One Symbol, pp. 160-174 in Gheorghe, M et al. Membrane Computing, CMC11, LNCS 6501, Springer Verlag Berlin-Heidelberg, 2010
Vaszil, Gy: On the Parallelizability of Languages Accepted by P automata, pp. 170-178, in Kelemenová, A ; Kelemen, J Computation, Cooperation and Life, Paun Festschrift, LNCS 6610, Springer-Verlag, Berlin-Heidelberg, 2011
Csuhaj-Varjú, E; Vaszil, Gy; Verlan, S: On Generalized Communicating P systems with One Symbol, pp. 137-154 in Gheorghe, M et al. Proc. Eleventh Conference on Membrane Computing, Verlag ProBusiness, Berlin, 2010
Vaszil, Gy: Variants of Distributed P automata and the Efficient Parallelizability of Languages. Abstract, pp. 43-50 in Gheorghe, M et al. Proc. Twelfth International Conference on Membrane Computing, Fontainebleau, Univ. of Paris Est Créteil Val de Marne, 2011
Csuhaj-Varjú, E: On Two Models in Bio-Inspired Computing: Membrane Systems and Networks of Evolutionary Processors, pp. 9-27 in Bel-Enguix, G et al. Biology, Computation, and Linguistics. New Interdisciplinary Paradigms. IOS Press, Amsterdam-Berlin-Tokyo-Washington, 2011
Csuhaj-Varjú, E; Gheorghe, M; Vaszil, Gy; Oswald, M: P Systems for Social Networks, pp. 113-124 in Martínez del Amor, A.M et al. Proc. Ninth Brainstorming Week on Membrane Computing, Sevilla, Fénix Editora, 2011
Csuhaj-Varjú, E; Vaszil, Gy: Expanding Formal Language and Automata Theory: Bio-inspired Computational Models, ERCIM News 85: 26, 2011
Ciencialová, L; Csuhaj-Varjú, E; Kelemenová, A; Vaszil, Gy: On Very Simple P Colonies, pp. 97-108 in Gutiérrez-Escuder, R. et al. Proc. BWMC 2009, Sevilla, 2009, Vol. I, Fénix Editora, Sevilla, 2009
Csuhaj-Varjú, E: On Two Models in Bio-Inspired Computing: Membrane Systems and Networks of Evolutionary Processors, pp. 9-27 in Bel-Enguix, G et al. Biology, Computation, and Linguistics. New Interdisciplinary Paradigms. IOS Press, Amsterdam-Berlin-Tokyo-Washington, ISBN 978-160750761, 2011
Csuhaj-Varjú, E; Vaszil, Gy: Finite dP Automata versus Multi-head Finite Automata, pp. 120-138 in Gheorghe, M et al. Membrane Computing - 12th International Conference, CMC 2011, LNCS 7184, Springer, 2012
Vaszil, Gy: Variants of distributed P automata and the efficient parallelizability of languages, pp. 51-61 in Gheorghe, M et al. Membrane Computing - 12th International Conference, CMC 2011, LNCS 7184, Springer, 2012
Csuhaj-Varjú, E; Gheorghe, M; Stannett, M: P Systems Controlled by General Topologies, pp. 70-81 in Durand-Lose, J; Jonoska, N Unconventional Computation and Natural Computation, LNCS 7445, Springer, 2012
Csuhaj-Varjú, E: P and dP Automata: Unconventional versus Classical Automata, pp. 7-22 in Yen, H-C; Ibarra, O-H; Developments in Language Theory - 16th International Conference, DLT, LNCS 7410, Springer, 2012
Csuhaj-Varjú, E; Vaszil, Gy: On the Power of P Automata, pp. 55-66 in Mauri, G. et al. Unconventional Computation and Natural Computation-12th International Conference, LNCS 7956, Springer, 2013
Csuhaj-Varjú, E: P Automata: Automata-like constructs modeling complex natural systems, pp. 13-30 in Bensch, S et al. Fifth Workshop on Non-Classical Models for Automata and Applications, NCMA 2013, series books@ocg.at, volume 294, OCG, ISBN 978-3-8540, 2013
Csuhaj-Varjú, E; Vaszil, Gy: On Counter Machines versus dP Automata, pp. 117-129 in Alhazov, A. et al. 14th International Conference on Membrane Computing CMC14, Inst. Math and Comp. Sci, Academy of Sciences of Moldova, ISBN 978-9975-4237, 2013
Csuhaj-Varjú, E: P and DP Automata: Unconventional versus Classical Automata, International Journal of Foundations of Computer Science 24(7): 995-1008, 2013
Kutrib, M; Provillard, J; Vaszil, Gy: Deterministic one-way Turing machines with sublinear space bounds, pp. 195-208 in Bensch, S et al. Fifth Workshop on Non-Classical Models for Automata and Applications, NCMA 2013, series books@ocg.at, volume 294, OCG, ISBN 978-3-85, 2013
Fésüs, M; Vaszil, Gy: Chemical programming and membrane systems, pp. 313-316, in Alhazov, A. et al. 14th International Conference on Membrane Computing CMC14, Inst. Math and Comp. Sci, Academy of Sciences of Moldova, ISBN 978-9975-4237, 2013
Csuhaj-Varjú, E; Vaszil, Gy: On Counter Machines versus dP Automata, pp. 138-150, in Alhazov, A. et al. Membrane Computing - 14th International Conference, CMC 2013, LNCS 8340, Springer, 2014
Csuhaj-Varjú, E; Vaszil, Gy: P Automata with Restricted Power, International Journal of Foundations of Computer Science 25(4): 391-408, 2014
Cienciala, L; Ciencialová, L; Csuhaj-Varjú, E: Towards P colonies Processing Strings, pp. 103-118 in Macias-Ramos, L.F. et al. Twelfth Brainstorming Week on Membrane Computing, RGNC REPORT 1/2014, Sevilla University, Fénix Editora, ISBN 978-84-940056, 2014
Csuhaj-Varjú, E; Gheorghe, M; Vaszil, Gy: P Systems: A Formal Approach to Social Networks (Abstract), pp. 7-10, in Gheorghe, M et al. 15th Int. Conference on Membrane Computing CMC15, Proc., Inst. of Comp. Science, Silesian University at Opava, ISBN 978-80-7510-036-8, 2014
Battyányi, P; Vaszil, Gy: Describing Membrane Computations with a Chemical Calculus, pp. 79-90, in Macias-Ramos, L.F. et al. Twelfth Brainstorming Week on Membrane Computing, RGNC REPORT 1/2014, Sevilla University, Fénix Editora, ISBN 978-84-940056, 2014
Kántor, K; Vaszil, Gy: Generalized P colony Automata, Journal of Automata, Languages and Combinatorics 19(1-4):145-156, 2014
Ciencialová, L; Csuhaj-Varjú, E; Kelemenová, A; Vaszil, Gy: On Very Simple P Colonies, pp. 97-108 in Gutiérrez-Escuder R. et al. Proc. BWMC 2009, Sevilla, 2009, Vol. I, Fénix Editora, Sevilla, 2009
Csuhaj-Varjú, E; Verlan, S: Power and Size of Generalized Communicating P Systems with Minimal Interaction Rules, pp. 547-552 in Paun, Gh et al. Proc. 10th Workshop on Membrane Computing, WMC10, RGNC Report 3/2009, Universidad de Sevilla, 2009
Ciencialová, L; Csuhaj-Varjú, E; Kelemenová, A; Vaszil, Gy: Variants of P Colonies with Very Simple Cell Structure, Int. J. of Computers, Communications & Control IV (3): 224-233, 2009



vissza »