License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.14
URN: urn:nbn:de:0030-drops-94773
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9477/
Chalk, Cameron ;
Luchsinger, Austin ;
Schweller, Robert ;
Wylie, Tim
Self-Assembly of Any Shape with Constant Tile Types using High Temperature
Abstract
Inspired by nature and motivated by a lack of top-down tools for precise nanoscale manufacture, self-assembly is a bottom-up process where simple, unorganized components autonomously combine to form larger more complex structures. Such systems hide rich algorithmic properties - notably, Turing universality - and a self-assembly system can be seen as both the object to be manufactured as well as the machine controlling the manufacturing process. Thus, a benchmark problem in self-assembly is the unique assembly of shapes: to design a set of simple agents which, based on aggregation rules and random movement, self-assemble into a particular shape and nothing else. We use a popular model of self-assembly, the 2-handed or hierarchical tile assembly model, and allow the existence of repulsive forces, which is a well-studied variant. The technique utilizes a finely-tuned temperature (the minimum required affinity required for aggregation of separate complexes).
We show that calibrating the temperature and the strength of the aggregation between the tiles, one can encode the shape to be assembled without increasing the number of distinct tile types. Precisely, we show one tile set for which the following holds: for any finite connected shape S, there exists a setting of binding strengths between tiles and a temperature under which the system uniquely assembles S at some scale factor. Our tile system only uses one repulsive glue type and the system is growth-only (it produces no unstable assemblies). The best previous unique shape assembly results in tile assembly models use O(K(S)/(log K(S))) distinct tile types, where K(S) is the Kolmogorov (descriptional) complexity of the shape S.
BibTeX - Entry
@InProceedings{chalk_et_al:LIPIcs:2018:9477,
author = {Cameron Chalk and Austin Luchsinger and Robert Schweller and Tim Wylie},
title = {{Self-Assembly of Any Shape with Constant Tile Types using High Temperature}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {14:1--14:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9477},
URN = {urn:nbn:de:0030-drops-94773},
doi = {10.4230/LIPIcs.ESA.2018.14},
annote = {Keywords: self-assembly, molecular computing, tiling, tile, shapes}
}
|
Keywords: |
|
self-assembly, molecular computing, tiling, tile, shapes |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
