### 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 0(1) that is capable of uniquely assembling essentially any n × 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 Ω(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(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.

Original language | English (US) |
---|---|

Pages | 571-580 |

Number of pages | 10 |

DOIs | |

State | Published - Feb 28 2006 |

Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |

### Other

Other | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | Miami, FL |

Period | 1/22/06 → 1/24/06 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

*Reducing tile complexity for self-assembly through temperature programming*. 571-580. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States. https://doi.org/10.1145/1109557.1109620