REAL

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.

[img]
Preview
PDF
42529_ZJ1.pdf

Download (102Kb)

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.

Item Type: Monograph (Project Report)
Uncontrolled Keywords: Számítástudomány
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Mr. Andras Holl
Date Deposited: 08 May 2009 11:00
Last Modified: 30 Nov 2010 22:04
URI: http://real.mtak.hu/id/eprint/649

Actions (login required)

View Item View Item