Computer Science – Computational Complexity
Scientific paper
2010-01-18
Computer Science
Computational Complexity
Scientific paper
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.
Lutz Jack H.
Shutters Brad
No associations
LandOfFree
Approximate Self-Assembly of the Sierpinski Triangle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximate Self-Assembly of the Sierpinski Triangle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Self-Assembly of the Sierpinski Triangle will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-659422