Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MOLECULAR COMPUTING:
Reports tagged with molecular computing:
TR08-031 | 14th January 2008
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

Computability and Complexity in Self-Assembly

This paper explores the impact of geometry on computability =
and complexity in
Winfree's model of nanoscale self-assembly. We work in the =
two-dimensional
tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =
first
main theorem says that there is a roughly quadratic function f ... more >>>


TR08-035 | 18th February 2008
James I. Lathrop, Jack H. Lutz, Scott M. Summers

Strict Self-Assembly of Discrete Sierpinski Triangles

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely ... more >>>


TR10-032 | 19th January 2010
Jack H. Lutz, Brad Shutters

Approximate Self-Assembly of the Sierpinski Triangle

The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex (typically aperiodic) DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in ... more >>>




ISSN 1433-8092 | Imprint