Reducing Tile Complexity for Self-Assembly Through Temperature Programming
<|reference_start|>Reducing Tile Complexity for Self-Assembly Through Temperature Programming: 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.<|reference_end|>
@article{kao2006reducing,
    title={Reducing Tile Complexity for Self-Assembly Through Temperature
  Programming},
    author={Ming-Yang Kao, Robert Schweller},
    journal={arXiv preprint arXiv:cs/0602010},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0602010},
    primaryClass={cs.CC}
}