CaltechAUTHORS
  A Caltech Library Service

String tile models for DNA computing by self-assembly

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 3540420762. https://resolver.caltech.edu/CaltechAUTHORS:20111024-092612665

[img]
Preview
PDF - Submitted Version
See Usage Policy.

649Kb

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:
URLURL TypeDescription
http://dx.doi.org/10.1007/3-540-44992-2_6DOIUNSPECIFIED
http://www.springerlink.com/content/m6p32bcpldkghx4f/PublisherUNSPECIFIED
ORCID:
AuthorORCID
Winfree, Erik0000-0002-5899-7523
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.
Series Name:Lecture Notes in Computer Science
Issue or Number:2054
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:03 Oct 2019 03:23

Repository Staff Only: item control page