Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
From MaRDI portal
Abstract: This paper concerns the self-assembly of scaled-up versions of arbitrary finite shapes. We work in the multiple temperature model that was introduced by Aggarwal, Cheng, Goldwasser, Kao, and Schweller (Complexities for Generalized Models of Self-Assembly, SODA 2004). The multiple temperature model is a natural generalization of Winfree's abstract tile assembly model, where the temperature of a tile system is allowed to be shifted up and down as self-assembly proceeds. We first exhibit two constant-size tile sets in which scaled-up versions of arbitrary shapes self-assemble. Our first tile set has the property that each scaled shape self-assembles via an asymptotically "Kolmogorov-optimum" temperature sequence but the scaling factor grows with the size of the shape being assembled. In contrast, our second tile set assembles each scaled shape via a temperature sequence whose length is proportional to the number of points in the shape but the scaling factor is a constant independent of the shape being assembled. We then show that there is no constant-size tile set that can uniquely assemble an arbitrary (non-scaled, connected) shape in the multiple temperature model, i.e., the scaling is necessary for self-assembly. This answers an open question of Kao and Schweller (Reducing Tile Complexity for Self-Assembly Through Temperature Programming, SODA 2006), who asked whether such a tile set existed.
Recommendations
- Reducing tile complexity for self-assembly through temperature programming
- Complexities for high-temperature two-handed tile self-assembly
- Self-assembly of any shape with constant tile types using high temperature
- Thermodynamically favorable computation via tile self-assembly
- Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models
- Self-Replication via Tile Self-Assembly (Extended Abstract).
Cites work
- scientific article; zbMATH DE number 1342108 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- Complexity of Self‐Assembled Shapes
- DNA Computing
- DNA Computing
- Intrinsic universality in self-assembly
- On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
- Randomized Self-assembly for Approximate Shapes
- Randomized self-assembly for exact shapes
- Reducing tile complexity for self-assembly through temperature programming
- Running time and program size for self-assembled squares
- Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
- Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
- Strict self-assembly of discrete Sierpinski triangles
- The program-size complexity of self-assembled squares (extended abstract)
Cited in
(19)- An introduction to tile-based self-assembly and a survey of recent results
- Step-wise tile assembly with a constant number of tile types
- Parallelism and time in hierarchical self-assembly
- Nearly constant tile complexity for any shape in two-handed tile assembly
- Parallelism and time in hierarchical self-assembly
- Reducing tile complexity for self-assembly through temperature programming
- Size-dependent tile self-assembly: constant-height rectangles and stability
- The need for seed (in the abstract Tile Assembly Model)
- The complexity of multiple handed self-assembly
- Universal computation and optimal construction in the chemical reaction network-controlled tile assembly model
- A study on complexity measure of diamond tile self-assembly system
- Program size and temperature in self-assembly
- DNA Computing
- scientific article; zbMATH DE number 6351478 (Why is no real title available?)
- Complexities for high-temperature two-handed tile self-assembly
- Parallel Computation Using Active Self-assembly
- Parallel computation using active self-assembly
- Self-assembly of any shape with constant tile types using high temperature
- Iterative self-assembly with dynamic strength transformation and temperature control
This page was built for publication: Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429337)
