Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems
From MaRDI portal
Publication:2003454
DOI10.1007/978-3-319-08123-6_30zbMATH Open1415.68101arXiv1404.7410OpenAlexW1550621477MaRDI QIDQ2003454FDOQ2003454
Authors: Andrew Winslow 
Publication date: 8 July 2019
Published in: Natural Computing, Unconventional Computation and Natural Computation (Search for Journal in Brave)
Abstract: We introduce a new property of tile self-assembly systems that we call size-separability. A system is size-separable if every terminal assembly is a constant factor larger than any intermediate assembly. Size-separability is motivated by the practical problem of filtering completed assemblies from a variety of incomplete "garbage" assemblies using gel electrophoresis or other mass-based filtering techniques. Here we prove that any system without cooperative bonding assembling a unique mismatch-free terminal assembly can be used to construct a size-separable system uniquely assembling the same shape. The proof achieves optimal scale factor and temperature for the size-separable system. As part of the proof, we obtain two results of independent interest on mismatch-free temperature-1 two-handed systems.
Full work available at URL: https://arxiv.org/abs/1404.7410
Recommendations
- Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems
- Program size and temperature in self-assembly
- Program size and temperature in self-assembly
- Size-dependent tile self-assembly: constant-height rectangles and stability
- Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
Cites Work
- Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM
- Intrinsic universality in self-assembly
- The program-size complexity of self-assembled squares (extended abstract)
- Polyomino-Safe DNA Self-assembly via Block Replacement
- Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes
- Intrinsic universality in tile self-assembly requires cooperation
- Shape replication through self-assembly and RNase enzymes
- Complexity of Self‐Assembled Shapes
- Parallelism and time in hierarchical self-assembly
- Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
- Producibility in hierarchical self-assembly
- Computability and Complexity in Self-assembly
- Limitations of Self-assembly at Temperature One
- Polyomino-safe DNA self-assembly via block replacement
- Staged self-assembly and polyomino context-free grammars
Cited In (3)
This page was built for publication: Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003454)
