Watson-Crick DOL systems: generative power and undecidable problems

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F03%3A%230001883" target="_blank" >RIV/47813059:19240/03:#0001883 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Watson-Crick DOL systems: generative power and undecidable problems
Original language description
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.
Czech name
Watson-Crickovy D0L systémy: generativní síla a nerozhodnutelné problémy
Czech description
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.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

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

Similar results(10)