×

DNA computing, sticker systems, and universality. (English) Zbl 0904.68127

Summary: We introduce the sticker systems, a computability model, which is an abstraction of the computations using the Watson-Crick complementarity as in Adleman’s DNA computing experiment. Several types of sticker 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 strictly intermediate power.

MSC:

68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

sticker systems
PDF BibTeX XML Cite
Full Text: DOI