Universal Computation with Watson-Crick D0L Systems

Kód výsledku v IS VaVaI

RIV/47813059:19240/02:50000002 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Universal Computation with Watson-Crick D0L Systems

Popis výsledku v původním jazyce

Watson-Crick D0L systems, introduced in 1997 by Mihalache and Salomaa, arise from two major principles: the Lindenmayer rewriting and the Watson-Crick complementarity principle. Complementarity can be viewed as a purely language-theroetic operation. Majority of a certain type of symbols in a string (purines vs. pyrimidines) triggers a transition to the complementary string. The paper deals with an expressive power of deterministic interactionless Watson-Crick Lindenmayer systems. A rather suprising result is obtained: these systems, consisting of iterated morphism and basic DNA operation, are able to compute any Turing computable function.

Název v anglickém jazyce

Universal Computation with Watson-Crick D0L Systems

Popis výsledku anglicky

Watson-Crick D0L systems, introduced in 1997 by Mihalache and Salomaa, arise from two major principles: the Lindenmayer rewriting and the Watson-Crick complementarity principle. Complementarity can be viewed as a purely language-theroetic operation. Majority of a certain type of symbols in a string (purines vs. pyrimidines) triggers a transition to the complementary string. The paper deals with an expressive power of deterministic interactionless Watson-Crick Lindenmayer systems. A rather suprising result is obtained: these systems, consisting of iterated morphism and basic DNA operation, are able to compute any Turing computable function.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

GP201/02/P079: Distribuované modely kognitivních výpočtů

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2002

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

289

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

16

Strana od-do

485-501

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—