Biológiai indíttatású kiszámítás: formális nyelvi modellek = Bio-inspired computation: formal language theoretic models

Csuhaj Varjú, Erzsébet and Vaszil, György (2007) Biológiai indíttatású kiszámítás: formális nyelvi modellek = Bio-inspired computation: formal language theoretic models. Project Report. OTKA.

Preview

PDF 42529_ZJ1.pdf Download (104kB)

Abstract

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. | 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.

Actions (login required)

Edit Item