Optimal Self-Assembly of Finite Shapes at Temperature 1 in 3D
Autor: | Scott M. Summers, David Furcy |
---|---|
Rok vydání: | 2016 |
Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences General Computer Science Computation 0102 computer and information sciences 02 engineering and technology Type (model theory) 01 natural sciences Set (abstract data type) Combinatorics Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Representation (mathematics) Mathematics Discrete mathematics Applied Mathematics Probabilistic logic 021001 nanoscience & nanotechnology Computer Science Applications 010201 computation theory & mathematics visual_art Theory of computation visual_art.visual_art_medium Computer Science - Computational Geometry Tile Self-assembly 0210 nano-technology |
Zdroj: | Algorithmica. 80:1909-1963 |
ISSN: | 1432-0541 0178-4617 |
DOI: | 10.1007/s00453-016-0260-6 |
Popis: | Tile self-assembly in which tiles may bind in a non-cooperative fashion is often referred to as “temperature 1 self-assembly” or simply “non-cooperative self-assembly”. In this type of self-assembly, a tile may non-cooperatively bind to an assembly via (at least) one of its sides, unlike in cooperative self-assembly, in which some tiles may be required to bind on two or more sides. Cooperative self-assembly leads to highly non-trivial theoretical behavior but two-dimensional non-cooperative self-assembly is conjectured to be only capable of producing highly-regular shapes and patterns, which, in general, cannot be interpreted as complex computation. Remarkably, Cook et al. (Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D. In: Proceedings of the 22nd Annual ACM–SIAM Symposium on Discrete Algorithms 2011) showed that three-dimensional non-cooperative self-assembly is essentially as powerful as cooperative self-assembly, with respect to Turing universality and self-assembly of $$N \times N$$ squares. In this paper, we consider the non-cooperative self-assembly of just-barely 3D shapes. Working in a three-dimensional variant of Winfree’s abstract Tile Assembly Model, we show that, for an arbitrary finite, connected shape $$X \subset {\mathbb {Z}}^2$$ , there is a tile set that uniquely self-assembles at temperature 1 into a 3D representation of a scaled-up version of X with optimal program-size complexity, where the “program-size complexity”, also known as “tile complexity”, of a shape is the minimum number of tile types required to uniquely self-assemble it. Moreover, our construction is “just barely” 3D in the sense that it only places tiles in the $$z = 0$$ and $$z = 1$$ planes. Our result is essentially a just-barely 3D temperature 1 simulation of a similar 2D temperature 2 result by Soloveichik and Winfree (SIAM J Comput 36(6):1544–1569, 2007). |
Databáze: | OpenAIRE |
Externí odkaz: |