Reducing tile complexity for self-assembly through temperature programming

Ming-Yang Kao*, Robert Schweller

*Corresponding author for this work

Research output: Contribution to conferencePaper

55 Citations (Scopus)

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 languageEnglish (US)
Pages571-580
Number of pages10
DOIs
StatePublished - Feb 28 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityMiami, FL
Period1/22/061/24/06

Fingerprint

Self-assembly
Tile
Self assembly
Programming
Temperature
Assembly Systems
Binary
Decrease
Arbitrary

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Kao, M-Y., & Schweller, R. (2006). 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
Kao, Ming-Yang ; Schweller, Robert. / Reducing tile complexity for self-assembly through temperature programming. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States.10 p.
@conference{d95014beb9aa40f2bdeff0dc8e3e91d4,
title = "Reducing tile complexity for self-assembly through temperature programming",
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.",
author = "Ming-Yang Kao and Robert Schweller",
year = "2006",
month = "2",
day = "28",
doi = "10.1145/1109557.1109620",
language = "English (US)",
pages = "571--580",
note = "Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 22-01-2006 Through 24-01-2006",

}

Kao, M-Y & Schweller, R 2006, 'Reducing tile complexity for self-assembly through temperature programming' Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States, 1/22/06 - 1/24/06, pp. 571-580. https://doi.org/10.1145/1109557.1109620

Reducing tile complexity for self-assembly through temperature programming. / Kao, Ming-Yang; Schweller, Robert.

2006. 571-580 Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Reducing tile complexity for self-assembly through temperature programming

AU - Kao, Ming-Yang

AU - Schweller, Robert

PY - 2006/2/28

Y1 - 2006/2/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33244476315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33244476315&partnerID=8YFLogxK

U2 - 10.1145/1109557.1109620

DO - 10.1145/1109557.1109620

M3 - Paper

AN - SCOPUS:33244476315

SP - 571

EP - 580

ER -

Kao M-Y, Schweller R. Reducing tile complexity for self-assembly through temperature programming. 2006. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States. https://doi.org/10.1145/1109557.1109620