Published 2001
| Submitted
Book Section - Chapter
Open
String tile models for DNA computing by self-assembly
- Creators
-
Winfree, Erik
- Eng, Tony
- Rozenberg, Grzegorz
- Other:
- Condon, Anne
Abstract
This paper investigates computation by linear assemblies of complex DNA tiles, which we call string tiles. By keeping track of the strands as they weave back and forth through the assembly, we show that surprisingly sophisticated calculations can be performed using linear self-assembly. Examples range from generating an addition table to providing O(1) solutions to CNF-SAT and DHPP. We classify the families of languages that can be generated by various types of DNA molecules, and establish a correspondence to the existing classes ET0L_(ml) and ET0L_(fin). Thus, linear self-assembly of string tiles can generate the output languages of finite-visit Turing Machines.
Additional Information
© 2001 Springer-Verlag Berlin Heidelberg. The authors are indebted to Joost Engelfriet and Hendrik Jan Hoogeboom for their guidance through the maze of results on the output languages of various sorts of transducers, and to John Reif and Thorn LaBean for their critical reading, discussion, and encouragement.Attached Files
Submitted - stringtiles_preprint.pdf
Files
stringtiles_preprint.pdf
Files
(664.6 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:1f3897cd82ce5c03ceb89b33545e62f0
|
664.6 kB | Preview Download |
Additional details
- Eprint ID
- 27367
- Resolver ID
- CaltechAUTHORS:20111024-092612665
- Created
-
2011-10-26Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 2054