Reducing Tile Complexity for Self-Assembly Through Temperature Programming

Details Reducing Tile Complexity for Self-Assembly Through Temperature Programming Reducing Tile Complexity for Self-Assembly Through Temperature Programming

2006-02-05

arxiv.org/abs/cs/0602010v1

Computer Science

Computational Complexity

A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA

Scientific paper

We consider the tile self-assembly model and how tile complexity can be eliminated by permitting the temperature of the self-assembly system to be adjusted throughout the assembly process. To do this, we propose novel techniques for designing tile sets that permit an arbitrary length $m$ binary number to be encoded into a sequence of $O(m)$ temperature changes such that the tile set uniquely assembles a supertile that precisely encodes the corresponding binary number. As an application, we show how this provides a general tile set of size O(1) that is capable of uniquely assembling essentially any $n\times n$ square, where the assembled square is determined by a temperature sequence of length $O(\log n)$ that encodes a binary description of $n$. This yields an important decrease in tile complexity from the required $\Omega(\frac{\log n}{\log\log n})$ for almost all $n$ when the temperature of the system is fixed. We further show that for almost all $n$, no tile system can simultaneously achieve both $o(\log n)$ temperature complexity and $o(\frac{\log n}{\log\log n})$ tile complexity, showing that both versions of an optimal square building scheme have been discovered. This work suggests that temperature change can constitute a natural, dynamic method for providing input to self-assembly systems that is potentially superior to the current technique of designing large tile sets with specific inputs hardwired into the tileset.

Affiliated with

Also associated with

No associations

Rating

Reducing Tile Complexity for Self-Assembly 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 Self-Assembly 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 Self-Assembly Through Temperature Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-361695