Watson-Crickovy D0L systémy: generativní síla a nerozhodnutelné problémy
Popis výsledku
Watson-Crickovy D0L systémy jsou formalismem inspirovaným přírodními procesy v DNA. Jsou studovány jejich vlastnosti a výpočetní síla. Ukážeme poměrně překvapivý výsledek, že tyto systémy mohou simulovat Minského registrový stroj a tím generovat (pomocíprojekce) všechny rekurzívně vyčíslitelné jazyky. Rovněž studujeme nerozhodnutelné problémy spojené s těmito systémy.
Klíčová slova
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Watson-Crick DOL systems: generative power and undecidable problems
Popis výsledku v původním jazyce
The properties of Watson-Crick DOL system, a language-theoretical formalism inspired by natural DNA processing, are studied. The model incorporates the iterated DOL-like morphism and the DNA complementarity principle represented by a letter-to-letter morphism. These two morphisins are connected by a natural condition called the trigger. We show first that this very simple model has rather unexpected power; it can closely and simply simulate any Minsky register machine. As a consequence, any recursivelyenumerable language can be obtained as a projection of the language of some standard Watson-Crick DOL system. Finally, we show that the graph reachability problem, equivalence problems and some other problems of standard Watson-Crick DOL systems are undecidable.
Název v anglickém jazyce
Watson-Crick DOL systems: generative power and undecidable problems
Popis výsledku anglicky
The properties of Watson-Crick DOL system, a language-theoretical formalism inspired by natural DNA processing, are studied. The model incorporates the iterated DOL-like morphism and the DNA complementarity principle represented by a letter-to-letter morphism. These two morphisins are connected by a natural condition called the trigger. We show first that this very simple model has rather unexpected power; it can closely and simply simulate any Minsky register machine. As a consequence, any recursivelyenumerable language can be obtained as a projection of the language of some standard Watson-Crick DOL system. Finally, we show that the graph reachability problem, equivalence problems and some other problems of standard Watson-Crick DOL systems are undecidable.
Klasifikace
Druh
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2003
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ů
Údaje specifické pro druh výsledku
Název periodika
THEORETICAL COMPUTER SCIENCE
ISSN
0304-3975
e-ISSN
—
Svazek periodika
1
Číslo periodika v rámci svazku
306
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
12
Strana od-do
—
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—
Základní informace
Druh výsledku
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP
IN - Informatika
Rok uplatnění
2003