On the effects of hierarchical self-assembly for reducing program-size complexity

DOI10.1016/j.tcs.2021.09.011MaRDI QIDQ2243581

David Furcy, Andrew Winslow, Sarah Eisenstat, Scott M. Summers, Martin L. Demaine, Matthew J. Patitz, Erik D. Demaine, Robert T. Schweller, Sarah M. Cannon

Publication date: 11 November 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.09.011

zbMATH Keywords

algorithmic self-assembly; hierarchical self-assembly; abstract tile assembly model

Mathematics Subject Classification ID

68Qxx: Theory of computing

Related Items

Unique assembly verification in two-handed self-assembly, The need for seed (in the abstract Tile Assembly Model)

Cites Work

• Unnamed Item
• Unnamed Item
• The two-handed tile assembly model is not intrinsically universal
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Self-assembly of discrete self-similar fractals
• Strict self-assembly of discrete Sierpinski triangles
• Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals
• Nearly constant tile complexity for any shape in two-handed tile assembly
• Scaled pier fractals do not strictly self-assemble
• Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly
• Self-assembly with Geometric Tiles
• The Power of Duples (in Self-Assembly): It’s Not So Hip to Be Square
• ASYNCHRONOUS SIGNAL PASSING FOR TILE SELF-ASSEMBLY: FUEL EFFICIENT COMPUTATION AND EFFICIENT ASSEMBLY OF SHAPES
• Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue
• Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)
• The program-size complexity of self-assembled squares (extended abstract)
• Programmable Control of Nucleation for Algorithmic Self-Assembly
• The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
• Computing in continuous space with self-assembling polygonal tiles (extended abstract)
• The Simulation Powers and Limitations of Higher Temperature Hierarchical Self-Assembly Systems*
• DNA Sticky End Design and Assignment for Robust Algorithmic Self-assembly
• Running time and program size for self-assembled squares
• Turing Universality of Step-Wise and Stage Assembly at Temperature 1
• Complexities for Generalized Models of Self-Assembly
• Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly