DNA COMPUTING, STICKER SYSTEMS, AND UNIVERSALITY

Authors
KARI L PAUN G ROZENBERG G SALOMAA A YU S
Citation
L. Kari et al., DNA COMPUTING, STICKER SYSTEMS, AND UNIVERSALITY, Acta informatica, 35(5), 1998, pp. 401-420
Citations number
19
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Acta informatica → ACNP
ISSN journal
00015903
Volume
35
Issue
5
Year of publication
1998
Pages
401 - 420
Database
ISI
SICI code
0001-5903(1998)35:5<401:DCSSAU>2.0.ZU;2-M
Abstract
We introduce the sticker systems, a computability model, which is an a bstraction of the computations using the Watson-Crick complementarity as in Adleman's DNA computing experiment, [1]. Several types of sticke r systems are shown to characterize (modulo a weak coding) the regular languages, hence the power of finite automata. One variant is proven to be equivalent to Turing machines. Another one is found to have a st rictly intermediate power.