Strict self-assembly of discrete Sierpinski triangles.

*(English)*Zbl 1160.68012Summary: E. Winfree [Algorithmic self-assembly of DNA. Ph.D. Thesis, California Institute of Technology (1998)] showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by P. W. K. Rothemund, N. Papadakis, and E. Winfree [“Algorithmic self-assembly of DNA Sierpinski triangles”, PLoS Biology 2(12) (2004)].

Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the strict self-assembly of discrete Sierpinski triangles, i.e., the task of tiling a discrete Sierpinski triangle and nothing else.

We first prove that the standard discrete Sierpinski triangle cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of D. Soloveichik and E. Winfree [SIAM J. Comput. 36, 1544–1569 (2007; Zbl 1136.68029).

Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the strict self-assembly of discrete Sierpinski triangles, i.e., the task of tiling a discrete Sierpinski triangle and nothing else.

We first prove that the standard discrete Sierpinski triangle cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of D. Soloveichik and E. Winfree [SIAM J. Comput. 36, 1544–1569 (2007; Zbl 1136.68029).

##### MSC:

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

52C20 | Tilings in \(2\) dimensions (aspects of discrete geometry) |

52C45 | Combinatorial complexity of geometric structures |

28A80 | Fractals |

PDF
BibTeX
XML
Cite

\textit{J. I. Lathrop} et al., Theor. Comput. Sci. 410, No. 4--5, 384--405 (2009; Zbl 1160.68012)

Full Text:
DOI

##### References:

[1] | L. Adleman, Towards a mathematical theory of self-assembly, Tech. Report, University of Southern California, 2000 |

[2] | Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, Paul W.K. Rothemund, Combinatorial optimization problems in self-assembly, in: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002, pp. 23-32 · Zbl 1192.90151 |

[3] | Leonard M. Adleman, Jarkko Kari, Lila Kari, Dustin Reishus, On the decidability of self-assembly of infinite ribbons, in: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 530-537 · Zbl 1191.68419 |

[4] | Apostol, T.M., () |

[5] | Qi Cheng, Ashish Goel, Pablo Moisset de Espanés, Optimal self-assembly of counters at temperature two, in: Proceedings of the First Conference on Foundations of Nanoscience: Self-assembled Architectures and Devices, 2004 |

[6] | Doty, D.; Gu, X.; Lutz, J.H.; Mayordomo, E.; Moser, P., Zeta-dimension, Proceedings of the thirtieth international symposium on mathematical foundations of computer science, (2005), Springer-Verlag, 283-294 |

[7] | Euler, L., Variae observationes circa series infinitas, Commentarii academiae scientiarum imperialis petropolitanae, 9, 160-188, (1737) |

[8] | Falconer, K., Fractal geometry: mathematical foundations and applications, (2003), Wiley · Zbl 1060.28005 |

[9] | Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren, Concrete mathematics, (1994), Addison-Wesley · Zbl 0836.00001 |

[10] | Hardy, G.; Wright, E., An introduction to the theory of numbers, (1979), Clarendon Press · Zbl 0423.10001 |

[11] | John H. Reif, Molecular assembly and computation: From theory to experimental demonstrations, in: Proceedings of the Twenty-Ninth International Colloquium on Automata, Languages and Programming, 2002, pp. 1-21 · Zbl 1056.68544 |

[12] | Paul W.K. Rothemund, Theory and experiments in algorithmic self-assembly, Ph.D. Thesis, University of Southern California, December 2001 |

[13] | Paul W.K. Rothemund, Erik Winfree, The program-size complexity of self-assembled squares (extended abstract), in: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000, pp. 459-468 · Zbl 1296.68051 |

[14] | Rothemund, Paul W.K.; Papadakis, Nick; Winfree, Erik, Algorithmic self-assembly of DNA sierpinski triangles, Plos biology, 2, 12, (2004) |

[15] | Seeman, N.C., Nucleic-acid junctions and lattices, Journal of theoretical biology, 99, 237-247, (1982) |

[16] | Soloveichik, David; Winfree, Erik, Complexity of self-assembled shapes, SIAM journal on computing, 36, 1544-1569, (2007) · Zbl 1136.68029 |

[17] | Wang, Hao, Proving theorems by pattern recognition — II, The Bell system technical journal, XL, 1, 1-41, (1961) |

[18] | Wang, Hao, Dominoes and the AEA case of the decision problem, (), 23-55 · Zbl 0137.01001 |

[19] | Willson, S.J., Growth rates and fractional dimensions in cellular automata, Physica D, 10, 69-74, (1984) |

[20] | Erik Winfree, Algorithmic self-assembly of DNA, Ph.D. Thesis, California Institute of Technology, June 1998 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.