Reducing Tile Complexity for Self-Assembly Through Temperature Programming

Published on: 2006/01/09

Abstract

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.

Authors

Ming-Yang Kao, Robert Schweller

File

Reducing Tile Complexity for Self-Assembly Through Temperature Programming