On the effects of hierarchical self-assembly for reducing program-size complexity
From MaRDI portal
Publication:2243581
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
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