Optimal staged self-assembly of general shapes

DOI10.1007/S00453-017-0318-0MaRDI QIDQ1751102zbMATH OpenOpenAlexFDO

Authors Eric Martinez, Luis Vega, Andrew Winslow, Tim Wylie, Cameron T. Chalk, Robert T. Schweller

Publication date 23 May 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.03919, https://drops.dagstuhl.de/opus/volltexte/2016/6377/

zbMATH Keywords

DNA computing2HAMhierarchicalbiocomputingstaging

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We analyze the number of tile types $t$, bins $b$, and stages necessary to assemble $nimesn$ squares and scaled shapes in the staged tile assembly model. For $nimesn$ squares, we prove $mathcalO(fraclogn-tb-tlogt{b}^2+fracloglogblogt)$ stages suffice and $Omega(fraclogn-tb-tlogt{b}^2)$ are necessary for almost all $n$. For shapes $S$ with Kolmogorov complexity $K(S)$, we prove $mathcalO(fracK(S)-tb-tlogt{b}^2+fracloglogblogt)$ stages suffice and $Omega(fracK(S)-tb-tlogt{b}^2)$ are necessary to assemble a scaled version of $S$, for almost all $S$. We obtain similarly tight bounds when the more powerful flexible glues are permitted.

Recommendations

• scientific article; zbMATH DE number 6846397
• Optimal staged self-assembly of linear assemblies
• Step-assembly with a constant number of tile types

Cites work

• scientific article; zbMATH DE number 6846397 (Why is no real title available?)
• A brief tour of theoretical tile self-assembly
• An introduction to Kolmogorov complexity and its applications
• An introduction to tile-based self-assembly and a survey of recent results
• Complexities for Generalized Models of Self-Assembly
• Complexity of Self‐Assembled Shapes
• Identifying shapes using self-assembly
• Intrinsic universality and the computational power of self-assembly
• One-dimensional staged self-assembly
• Optimal program-size complexity for self-assembly at temperature 1 in 3D
• Parallelism and time in hierarchical self-assembly
• Producibility in hierarchical self-assembly
• Running time and program size for self-assembled squares
• Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor (extended abstract)
• Shape replication through self-assembly and RNase enzymes
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Step-wise tile assembly with a constant number of tile types
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• The program-size complexity of self-assembled squares (extended abstract)
• Turing universality of step-wise and stage assembly at temperature 1
• Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM

Cited in

(13)

• Step-wise tile assembly with a constant number of tile types
• Complexity of Self‐Assembled Shapes
• Producibility in hierarchical self-assembly
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Simulation of multiple stages in single bin active tile self-assembly
• Step-assembly with a constant number of tile types
• Building squares with optimal state complexity in restricted active self-assembly
• Connected reconfiguration of lattice-based cellular structures by finite-memory robots
• Particle-based assembly using precise global control
• Optimal staged self-assembly of linear assemblies
• Optimal staged self-assembly of linear assemblies
• Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
• scientific article; zbMATH DE number 6846397 (Why is no real title available?)

This page was built for publication: Optimal staged self-assembly of general shapes

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