DNA computing, sticker systems, and universality |
| |
| Authors: | Lila Kari Gheorghe P?un Grzegorz Rozenberg Arto Salomaa Sheng Yu |
| |
| Affiliation: | (1) Department of Computer Science, University of Western Ontario, London, Ontario, Canada N6A 5B7 , CA;(2) Institute of Mathematics of the Romanian Academy, P.O. Box 1 – 764, RO-70700 Bucureşti, Romania , RO;(3) Department of Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands , NL;(4) Academy of Finland and Turku University, Department of Mathematics, FIN-20500 Turku, Finland , FI |
| |
| Abstract: | 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, 1]. 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.
Received: 10 October 1996 / 16 April 1997 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
