Reducing tile complexity for self-assembly through temperature programming

DOI10.1145/1109557.1109620MaRDI QIDQ3581583zbMATH OpenOpenAlexFDO

Authors Robert T. Schweller, Ming-Yang Kao

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0602010

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

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 O(1) that is capable of uniquely assembling essentially any $nimesn$ square, where the assembled square is determined by a temperature sequence of length $O(logn)$ that encodes a binary description of $n$. This yields an important decrease in tile complexity from the required $Omega(fraclognloglogn)$ 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(logn)$ temperature complexity and $o(fraclognloglogn)$ 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.

Recommendations

• Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• Nearly constant tile complexity for any shape in two-handed tile assembly
• Optimal program-size complexity for self-assembly at temperature 1 in 3D
• Program size and temperature in self-assembly

Cited in

(42)

• Path finding in the tile assembly model
• Complexities for high-temperature two-handed tile self-assembly
• Identifying shapes using self-assembly
• Tile complexity of approximate squares
• Parallel computation using active self-assembly
• Exponential replication of patterns in the signal tile assembly model
• The complexity of multiple handed self-assembly
• Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
• Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models
• Efficient 3-SAT algorithms in the tile assembly model
• Triangular and hexagonal tile self-assembly systems
• Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems
• Triangular tile self-assembly systems
• Randomized Self Assembly of Rectangular Nano Structures
• Exact shapes and Turing universality at temperature 1 with a single negative glue
• scientific article; zbMATH DE number 6351478 (Why is no real title available?)
• Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems
• A Self-assembly Model of Time-Dependent Glue Strength
• Connecting the Dots: Molecular Machinery for Distributed Robotics
• Self-assembly of Discrete Self-similar Fractals
• Program size and temperature in self-assembly
• Self-assembly of any shape with constant tile types using high temperature
• Parallel Computation Using Active Self-assembly
• Exponential replication of patterns in the signal tile assembly model
• Iterative self-assembly with dynamic strength transformation and temperature control
• Efficient algorithms for self assembling non-rectangular nano structures
• Self-assembly of decidable sets
• Parallelism and time in hierarchical self-assembly
• Parallelism and time in hierarchical self-assembly
• A minimal requirement for self-assembly of lines in polylogarithmic time
• Building squares with optimal state complexity in restricted active self-assembly
• Self-assembly of infinite structures: a survey
• The need for seed (in the abstract Tile Assembly Model)
• Complexity of graph self-assembly in accretive systems and self-destructible systems
• Polyominoes simulating arbitrary-neighborhood zippers and tilings
• Arithmetic computation in the tile assembly model: addition and multiplication
• Nondeterministic polynomial time factoring in the tile assembly model
• Solving NP-complete problems in the tile assembly model
• On the complexity of graph self-assembly in accretive systems
• Toward minimum size self-assembled counters
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Self-assembly of discrete self-similar fractals

This page was built for publication: Reducing tile complexity for self-assembly through temperature programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581583)