Temperature Programming

The multiple temperature model generalizes the tile self-assembly model by permitting the temperature of the system to shift up and down. Aggarwal et al. showed that by raising the temperature just once during the assembly process certain shapes could be uniquely assembled using fewer distinct tiles than what is possible for a model with a fixed temperature.

The Multiple Temperature Model

In the multiple temperature model, the integer temperature \(\tau\) in the tile system description is replaced with a sequence of integers called the temperature sequence of the system. The size of the largest temperature in the sequence is called the temperature range of the system. In a system with \(k\) temperatures, assembly takes place in \(k\) phases. In the first phase, assembly takes place as in the standard model under temperature \(\tau_1\). Phase 1 continues until no tiles can be added. In phase two, tiles can be added or removed under \(\tau_2\). Specifically, at any point during phase 2, if there exists a cut of the resultant supertile with cut strength less than \(\tau_2\), the portion of the supertile occurring on the side of the cut not containing the seed tile may be removed. Also, at any point in the second phase any tile in \(T\) may be added to the supertile if the tile is attachable at a given position under temperature \(\tau_2\). The second phase of this assembly continues until no tiles can be added or removed. We then go to phase 3 in which tiles may be added and removed under temperature \(\tau_3\). The process is continued up through \(\tau_k\). For any given choice of additions and removals such that each of the \(k\) phases finishes, the tile system terminally produces the corresponding shape assembled after phase \(k\). If the \(k\) phases always finish regardless of the choice of additions and removals, and the terminally produced supertile \(R\) is unique, the tile system uniquely assembles the shape of \(R\).

There exists a single tile set of constant size that can be efficiently programmed by a series of temperature changes to uniquely assembly essentially any \(n\) × \(n\) square.

References

[1] Ming-Yang Kao, Robert Schweller. Reducing Tile Complexity for Self-Assembly Through Temperature Programming.

[2] G. Aggarwal, Q. Cheng, M. H. Goldwasser, M.-Y. Kao, P. M. de Espanes, and R. T. Schweller. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34:1493–1515, 2005.

[3] G. Aggarwal, M. H. Goldwasser, M.-Y. Kao, and R. T. Schweller. Complexities for generalized models of self-assembly. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 880–889, 2004.