Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming

Details Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming

2009-07-07

arxiv.org/abs/0907.1307v1

Computer Science

Computational Complexity

Scientific paper

This paper concerns the self-assembly of scaled-up versions of arbitrary finite shapes. We work in the multiple temperature model that was introduced by Aggarwal, Cheng, Goldwasser, Kao, and Schweller (Complexities for Generalized Models of Self-Assembly, SODA 2004). The multiple temperature model is a natural generalization of Winfree's abstract tile assembly model, where the temperature of a tile system is allowed to be shifted up and down as self-assembly proceeds. We first exhibit two constant-size tile sets in which scaled-up versions of arbitrary shapes self-assemble. Our first tile set has the property that each scaled shape self-assembles via an asymptotically "Kolmogorov-optimum" temperature sequence but the scaling factor grows with the size of the shape being assembled. In contrast, our second tile set assembles each scaled shape via a temperature sequence whose length is proportional to the number of points in the shape but the scaling factor is a constant independent of the shape being assembled. We then show that there is no constant-size tile set that can uniquely assemble an arbitrary (non-scaled, connected) shape in the multiple temperature model, i.e., the scaling is necessary for self-assembly. This answers an open question of Kao and Schweller (Reducing Tile Complexity for Self-Assembly Through Temperature Programming, SODA 2006), who asked whether such a tile set existed.

Affiliated with

Also associated with

No associations

Rating

Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-319701