Strict self-assembly of fractals using multiple hands

DOI10.1007/S00453-015-0022-XzbMATH Open1348.68052arXiv1407.7900OpenAlexW1944056116MaRDI QIDQ334941FDOQ334941

Authors: Cameron T. Chalk, Dominic A. Fernandez, Alejandro Huerta, Mario A. Maldonado, Robert T. Schweller, Leslie Sweet 

Publication date: 1 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of the discrete Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the emph{$h$-handed assembly model} ($h$-HAM), which generalizes the 2-HAM to allow up to $h$ assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly model has yet been shown to strictly assemble an infinite fractal without significant modification to the fractal shape. In this paper we not only achieve this, but in the case of the Sierpinski carpet are able to achieve it within the 2-HAM, one of the most well studied tile assembly models in the literature. Our specific results are as follows. We provide a $6$-HAM construction for the Sierpinski triangle that works at scale factor 1, 30 tile types, and assembles the fractal in a emph{near perfect} way in which all intermediate assemblies are finite-sized iterations of the recursive fractal. We further assemble the Sierpinski triangle within the $3$-HAM at scale factor 3 and 990 tile types. For the Sierpinski carpet, we present a $2$-HAM result that works at scale factor 3 and uses 1,216 tile types. We further include analysis showing that the aTAM is incapable of strictly assembling the non-tree Sierpinski triangle considered in this paper, and that multiple hands are needed for the near-perfect assembly of the Sierpinski triangle and the Sierpinski carpet.

Full work available at URL: https://arxiv.org/abs/1407.7900

Recommendations

• Self-assembly of 4-sided fractals in the two-handed tile assembly model
• Strict Self-assembly of Discrete Sierpinski Triangles
• Strict self-assembly of discrete Sierpinski triangles
• Approximate self-assembly of the Sierpinski triangle
• Approximate self-assembly of the Sierpinski triangle

zbMATH Keywords

fractalsself-assemblyDNA tiles

Mathematics Subject Classification ID

Fractals (28A80)

Cites Work

• Strict self-assembly of discrete Sierpinski triangles
• Self-assembly with Geometric Tiles
• Title not available (Why is that?)
• Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor (extended abstract)
• One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
• Complexities for Generalized Models of Self-Assembly
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Intrinsic universality in tile self-assembly requires cooperation
• Title not available (Why is that?)
• Self-assembly of decidable sets
• DNA Computing
• Fuel Efficient Computation in Passive Self-Assembly
• Title not available (Why is that?)
• Approximate self-assembly of the Sierpinski triangle
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Self-assembly of discrete self-similar fractals
• A route to fractal DNA-assembly
• Scaled pier fractals do not strictly self-assemble
• Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes
• Scaled Tree Fractals Do not Strictly Self-assemble
• Producibility in Hierarchical Self-assembly
• Self-assembly of the discrete Sierpinski carpet and related fractals
• Self-assembling rulers for approximating generalized Sierpinski carpets

Cited In (13)

• Strict Self-assembly of Discrete Sierpinski Triangles
• Approximate self-assembly of the Sierpinski triangle
• 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
• Unique assembly verification in two-handed self-assembly
• Fractal dimension of assemblies in the abstract tile assembly model
• The complexity of multiple handed self-assembly
• Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles
• Self-assembly of 4-sided fractals in the two-handed tile assembly model
• Self-assembly of Discrete Self-similar Fractals
• Self-assembly of the discrete Sierpinski carpet and related fractals
• Hierarchical self-assembly of fractals with signal-passing tiles

This page was built for publication: Strict self-assembly of fractals using multiple hands

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