Approximate self-assembly of the Sierpinski triangle
From MaRDI portal
Publication:693068
DOI10.1007/978-3-642-13962-8_32zbMATH Open1279.68082arXiv1001.2888OpenAlexW2049281111MaRDI QIDQ693068FDOQ693068
Authors: Jack H. Lutz, Brad Shutters 
Publication date: 7 December 2012
Published in: Theory of Computing Systems, Programs, Proofs, Processes (Search for Journal in Brave)
Abstract: The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex (typically aperiodic) DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in the Sierpinski triangle. More recently, Lathrop, Lutz, and Summers proved that the Sierpinski triangle cannot self-assemble in the "strict" sense in which tiles are not allowed to appear at positions outside the target structure. Here we investigate the strict self-assembly of sets that approximate the Sierpinski triangle. We show that every set that does strictly self-assemble disagrees with the Sierpinski triangle on a set with fractal dimension at least that of the Sierpinski triangle (roughly 1.585), and that no subset of the Sierpinski triangle with fractal dimension greater than 1 strictly self-assembles. We show that our bounds are tight, even when restricted to supersets of the Sierpinski triangle, by presenting a strict self-assembly that adds communication fibers to the fractal structure without disturbing it. To verify this strict self-assembly we develop a generalization of the local determinism method of Soloveichik and Winfree.
Full work available at URL: https://arxiv.org/abs/1001.2888
Recommendations
Cites Work
- Strict self-assembly of discrete Sierpinski triangles
- The program-size complexity of self-assembled squares (extended abstract)
- Title not available (Why is that?)
- Complexity of Self‐Assembled Shapes
- Self-assembly of discrete self-similar fractals
- Four encounters with Sierpiński's gasket
- Self-assembly of the discrete Sierpinski carpet and related fractals
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2005
- The equality of fractional dimensions for certain cellular automata
- Defining Fractal Subsets of Z d
- Self-Affine Carpets on the Square Lattice
- Distribution of digits in integers: fractal dimensions and zeta functions
Cited In (22)
- An introduction to tile-based self-assembly and a survey of recent results
- Scaled pier fractals do not strictly self-assemble
- Strict Self-assembly of Discrete Sierpinski Triangles
- Self-assembling rulers for approximating generalized Sierpinski carpets
- Approximate self-assembly of the Sierpinski triangle
- Scaled Tree Fractals Do not Strictly Self-assemble
- Strict self-assembly of discrete Sierpinski triangles
- 3D fractal DNA assembly from coding, geometry and protection
- Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals
- Traversal languages capturing isomorphism classes of Sierpiński gaskets
- Triangular and hexagonal tile self-assembly systems
- Fractal dimension of assemblies in the abstract tile assembly model
- Self-assembly of infinite structures: a survey
- Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles
- Self-assembly of 4-sided fractals in the two-handed tile assembly model
- Strict self-assembly of fractals using multiple hands
- Self-assembling rulers for approximating generalized Sierpinski carpets
- Triangular tile self-assembly systems
- Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
- Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
- Hierarchical self-assembly of fractals with signal-passing tiles
- Optimal program-size complexity for self-assembled squares at temperature 1 in 3D
This page was built for publication: Approximate self-assembly of the Sierpinski triangle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693068)
