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 978-3-540-42076-7.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 ReadCube access
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.
Subject Keywords:Turing Machine; Maximal Assembly; Maximal Path; General Tile; Planar Tile
Series Name:Lecture Notes in Computer Science
Issue or Number:2054
Record Number:CaltechAUTHORS:20111024-092612665
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27367
Deposited By: Tony Diaz
Deposited On:26 Oct 2011 16:00
Last Modified:09 Nov 2021 16:48

Repository Staff Only: item control page