Winfree, Erik and Eng, Tony and Rozenberg, Grzegorz (2001) String tile models for DNA computing by self-assembly. In: DNA Computing. Lecture Notes in Computer Science. No.2054. Springer , Berlin, pp. 63-88. ISBN 978-3-540-42076-7. https://resolver.caltech.edu/CaltechAUTHORS:20111024-092612665
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Submitted Version
See Usage Policy. 664kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111024-092612665
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.
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| 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. | |||||||||
| Subject Keywords: | Turing Machine; Maximal Assembly; Maximal Path; General Tile; Planar Tile | |||||||||
| Series Name: | Lecture Notes in Computer Science | |||||||||
| Issue or Number: | 2054 | |||||||||
| DOI: | 10.1007/3-540-44992-2_6 | |||||||||
| Record Number: | CaltechAUTHORS:20111024-092612665 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20111024-092612665 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 27367 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 26 Oct 2011 16:00 | |||||||||
| Last Modified: | 09 Nov 2021 16:48 |
Repository Staff Only: item control page
