Randomized self-assembly for exact shapes
From MaRDI portal
Abstract: Working in Winfree's abstract tile assembly model, we show that a constant-size tile assembly system can be programmed through relative tile concentrations to build an n x n square with high probability, for any sufficiently large n. This answers an open question of Kao and Schweller (Randomized Self-Assembly for Approximate Shapes, ICALP 2008), who showed how to build an approximately n x n square using tile concentration programming, and asked whether the approximation could be made exact with high probability. We show how this technique can be modified to answer another question of Kao and Schweller, by showing that a constant-size tile assembly system can be programmed through tile concentrations to assemble arbitrary finite *scaled shapes*, which are shapes modified by replacing each point with a c x c block of points, for some integer c. Furthermore, we exhibit a smooth tradeoff between specifying bits of n via tile concentrations versus specifying them via hard-coded tile types, which allows tile concentration programming to be employed for specifying a fraction of the bits of "input" to a tile assembly system, under the constraint that concentrations can only be specified to a limited precision. Finally, to account for some unrealistic aspects of the tile concentration programming model, we show how to modify the construction to use only concentrations that are arbitrarily close to uniform.
Recommendations
- Randomized Self-assembly for Approximate Shapes
- Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models
- Tile complexity of approximate squares
- Randomized Self Assembly of Rectangular Nano Structures
- Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
Cited in
(25)- Identifying shapes using self-assembly
- Tile complexity of approximate squares
- Parallel computation using active self-assembly
- The complexity of multiple handed self-assembly
- Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
- An introduction to tile-based self-assembly and a survey of recent results
- Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models
- Fast algorithmic self-assembly of simple shapes using random agitation
- Flipping tiles: concentration independent coin flips in tile self-assembly
- Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems
- Randomized Self Assembly of Rectangular Nano Structures
- Exact shapes and Turing universality at temperature 1 with a single negative glue
- Random Number Selection in Self-assembly
- Randomized Self-assembly for Approximate Shapes
- The Tile Complexity of Linear Assemblies
- scientific article; zbMATH DE number 6846397 (Why is no real title available?)
- Program size and temperature in self-assembly
- Concentration independent random number generation in tile self-assembly
- scientific article; zbMATH DE number 7298599 (Why is no real title available?)
- Parallel Computation Using Active Self-assembly
- On Times to Compute Shapes in 2D Tile Self-assembly
- 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
- The need for seed (in the abstract Tile Assembly Model)
This page was built for publication: Randomized self-assembly for exact shapes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5390605)
