Biológiai indíttatású kiszámítás: formális nyelvi modellek
Title in English
Bio-inspired computation: formal language theoretic models
Panel
Mathematics and Computing Science
Department or equivalent
HUN-REN Institute for Computer Science and Control
Participants
Csima, Judit Vaszil, György
Starting date
2003-01-01
Closing date
2006-12-31
Funding (in million HUF)
4.027
FTE (full time equivalent)
0.00
state
closed project
Final report
Results in Hungarian
A biológiai indíttatású nyelvprocesszor hálózatok területén megmutattuk, hogy az elemi evolúciós processzorokból álló hibrid hálózatok a Turing gépekkel egyenlő számítási erejű eszközök. Bebizonyítottuk, hogy minden, azonos ábécé feletti rekurzíven felsorolható nyelv előállítható nem elemi evolúciós processzorok hasonló architektúrájú hibrid hálózatával. Az evolúciós processzorok kizárólagosan egy elemi genetikai művelet, azaz beszúrás, törlés vagy betűcsere elvégzésére alkalmas eszközök.
A membrán rendszerek elméletében megmutattuk, hogy a P automaták, amelyek kizárólag kommunikációra épülő elfogadó membrán rendszerek, szabályaik maximálisan párhuzamos módú használata esetén a környezetfüggő nyelvek osztályát, míg a szabályaik szekvenciális módú használata esetén egy, a logaritmikusnál kisebb tárigényű nyelvosztályt határoznak meg. A P rendszerek több fontos változatáról megmutattuk, hogy a Turing gépekével egyenlő számítási erejű, még bizonyos méretparamétereinek korlátozása esetén is.
A molekuláris számítástudomány területén megmutattuk a Watson-Crick komplementaritás elvére épülő ún. kiterjesztett standard Watson-Crick D0L rendszerek hálózatainak a Turing gépekével való egyenlő számítási erejét nem teljes információ közvetítésének lehetősége esetén is.
Results in English
In the area of bio-inspired language processors, we proved that hibrid networks of elementary evolutionary processors are computationally complete and these networks with non-elementary components are able to determine any recursively enumerable language over the same alphabet with a similar underlying graph structure. Evolutionary processors are language determining devices capable of performing only one type of point mutations (insertion, deletion, replacement).
In the theory of membrane (P) systems, we proved that P automata, i.e. accepting, purely communicating membrane systems, by applying their rules in the maximally parallel manner determine the class of context-sensitive languages and by using their rules sequentially identify a class of languages strictly included in the class of languages computable by Turing machines with a logarithmically bounded workspace. For several important variants of P systems, we proved that they are computationally complete, even if they are bounded in some of their size parameters.
In the area of molecular computing, we proved that networks of extended standard Watson-Crick D0L systems, models which make use of Watson-Crick complementarity, with the possibility of incomplete information communication are computationally complete.
Csuhaj-Varjú E; Margenstern M; Vaszil Gy: P Colonies with a Bounded Number of Cells and Programs, pp. 352-366 in: Hoogeboom, HJ et al. WMC7 2006, Revised, Selected and Invited Papers, Springer, Lect Notes Comput Sci. 4361, 2006
Csuhaj-Varjú E; Margenstern M; Vaszil Gy; Verlan S: On small universal antiport P systems, Theoretical Computer Science 372:152-164, 2007
Csuhaj-Varjú E; Petre I; Vaszil Gy: Self-assembly of strings and languages, Theoretical Computer Science, megjelenés alatt, online elérhető, DOI:10.1016/j.tcs.2006.12.004, 2007
Besozzi D; Csuhaj-Varjú E; Mauri G; Zandron C: On the power and size of extended gemmating P systems, Soft Computing 9(9): 650-656, 2005
Csuhaj-Varjú E; Martin-Vide C; Mitrana V: Hybrid networks of evolutionary processors are computationally complete, Acta Informatica 41: 257-272, 2005
Csuhaj-Varjú E; Vaszil Gy: Reducing the Size of Extended Gemmating P Systems, pp. 296-308 in: Mauri G et al. WMC5 2004, Revised, Selected and Invited Papers, Springer, Lect Notes Comput Sci. 3365, 2005
Csuhaj-Varjú E; Paun Gh; Vaszil Gy: Grammar Systems versus Membrane Computing: The Case of CD Grammar Systems, Fundamenta Informaticae 76(3): 271-292, 2007
Vaszil Gy: On a class of P automata as a machine model for languages over infinite alphabets, pp. 317-325 in Proc. Third Brainstorming Week on Membrane Computing, RGNC Report 01/2005, Fénix Editora, Sevilla, 2005
Csuhaj-Varjú E; Ibarra OH; Vaszil Gy: On the Computational Complexity of P Automata, pp. 76-89 in: Ferretti C;Mauri G; Zandron C. DNA Computing, DNA10, Revised Selected Papers, Springer, Lect Notes Comput Sci. 3384, 2005
Csuhaj-Varjú, E; Kelemen J; Kelemenová A; Paun Gh; Vaszil Gy: Computing with Cells in Environment: P Colonies, Journal of Multiple-Valued Logic and Soft Computing 12:201-215, 2006
Csuhaj-Varjú E; Ibarra OH; Vaszil Gy: On the Computational Complexity of P Automata, Natural Computing 5: 109-126, 2006
Csuhaj-Varjú E: Networks of Standard Watson-Crick D0L Systems with Incomplete Information Communication, pp. 35-38 in: Karhumaki J et al. Theory is Forever, Springer, Lect Notes Comput Sci. 3113, 2004
Csuhaj-Varjú, E; Vaszil Gy: New Results and Research Directions Concerning P Automata, Accepting P Systems with Communication Only, pp. 171-179 in Proc. Brainstorming Week on Membrane Computing, Univ. Rovira i Virgili, GRMLC, TR 26/03, Tarragona, 2003
Csuhaj-Varjú E: P Automata, pp. 19-35 in: Mauri G et al. WMC5 2004, Revised, Selected and Invited Papers, Springer, Lect Notes Comput Sci. 3365, 2005
Csuhaj-Varjú E; Paun Gh; Vaszil Gy: Tissue-like P systems with Dynamically Emerging Requests, közlésre benyújtva, 2007
Csuhaj-Varjú E; Di Nola A; Paun Gh; Pérez-Jiménez MJ; Vaszil Gy: Editing Configurations of P Systems, közlésre benyújtva, 2007
