Document Open Access Logo

Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems

Authors Ho-Lin Chen, David Doty, Ján Manuch, Arash Rafiey, Ladislav Stacho

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.360.pdf
  • Filesize: 0.93 MB
  • 14 pages

Document Identifiers

Author Details

Ho-Lin Chen
David Doty
Ján Manuch
Arash Rafiey
Ladislav Stacho

Cite As Get BibTex

Ho-Lin Chen, David Doty, Ján Manuch, Arash Rafiey, and Ladislav Stacho. Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 360-373, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.360

Abstract

We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap.

This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly and avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

Subject Classification

Keywords
  • self-assembly
  • hierarchical
  • pumping

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanés, and Robert T. Schweller. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34:1493-1515, 2005. Preliminary version appeared in SODA 2004. Google Scholar
  2. Robert D. Barish, Rebecca Schulman, Paul W. K. Rothemund, and Erik Winfree. An information-bearing seed for nucleating algorithmic self-assembly. Proceedings of the National Academy of Sciences, 106(15):6054-6059, March 2009. Google Scholar
  3. Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Andrew Winslow. Two hands are better than one (up to constant factors). In STACS 2013: Proceedings of the Thirtieth International Symposium on Theoretical Aspects of Computer Science, pages 172-184, 2013. Google Scholar
  4. Ho-Lin Chen and David Doty. Parallelism and time in hierarchical self-assembly. In SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1163-1182, 2012. Google Scholar
  5. Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, and Damien Woods. One tile to rule them all: Simulating any Turing machine, tile assembly system, or tiling system with a single puzzle piece. In ICALP 2014: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, 2014. Google Scholar
  6. Erik D. Demaine, Matthew J. Patitz, Trent Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods. The two-handed tile assembly model is not intrinsically universal. In ICALP 2013: Proceedings of the 40th International Colloquium on Automata, Languages and Programming, July 2013. Google Scholar
  7. David Doty. Theory of algorithmic self-assembly. Communications of the ACM, 55(12):78-88, December 2012. Google Scholar
  8. David Doty. Producibility in hierarchical self-assembly. In UCNC 2014: Proceedings of 13th Unconventional Computation and Natural Computation, 2014. Google Scholar
  9. David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, and Scott M. Summers. Strong fault-tolerance for self-assembly with fuzzy temperature. In FOCS 2010: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pages 417-426. IEEE, 2010. Google Scholar
  10. David Doty, Matthew J. Patitz, and Scott M. Summers. Limitations of self-assembly at temperature 1. Theoretical Computer Science, 412(1-2):145-158, January 2011. Preliminary version appeared in DNA 2009. Google Scholar
  11. Pierre Étienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, and Damien Woods. Intrinsic universality in tile self-assembly requires cooperation. In SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 752-771, 2014. Google Scholar
  12. Kei Goto, Yoko Hinob, Takayuki Kawashima, Masahiro Kaminagab, Emiko Yanob, Gaku Yamamotob, Nozomi Takagic, and Shigeru Nagasec. Synthesis and crystal structure of a stable S-nitrosothiol bearing a novel steric protection group and of the corresponding S-nitrothiol. Tetrahedron Letters, 41(44):8479-8483, 2000. Google Scholar
  13. Wilfried Heller and Thomas L. Pugh. "Steric protection" of hydrophobic colloidal particles by adsorption of flexible macromolecules. Journal of Chemical Physics, 22(10):1778, 1954. Google Scholar
  14. Wilfried Heller and Thomas L. Pugh. "Steric" stabilization of colloidal solutions by adsorption of flexible macromolecules. Journal of Polymer Science, 47(149):203-217, 1960. Google Scholar
  15. Chris Luhrs. Polyomino-safe DNA self-assembly via block replacement. Natural Computing, 9(1):97-109, March 2010. Preliminary version appeared in DNA 2008. Google Scholar
  16. Ján Maňuch, Ladislav Stacho, and Christine Stoll. Two lower bounds for self-assemblies at temperature 1. Journal of Computational Biology, 17(6):841-852, 2010. Google Scholar
  17. Matthew J. Patitz. An introduction to tile-based self-assembly. In UCNC 2012: Proceedings of the 11th international conference on Unconventional Computation and Natural Computation, pages 34-62, Berlin, Heidelberg, 2012. Springer-Verlag. Google Scholar
  18. John H. Reif and Tianqi Song. Complexity and computability of temperature-1 tilings. Poster at DNA 2013: 19th International Meeting on DNA Computing and Molecular Programming, 2013. Google Scholar
  19. Paul W. K. Rothemund and Erik Winfree. The program-size complexity of self-assembled squares (extended abstract). In STOC 2000: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 459-468, 2000. Google Scholar
  20. Rebecca Schulman and Erik Winfree. Synthesis of crystals with a programmable kinetic barrier to nucleation. Proceedings of the National Academy of Sciences, 104(39):15236-15241, 2007. Google Scholar
  21. Rebecca Schulman and Erik Winfree. Programmable control of nucleation for algorithmic self-assembly. SIAM Journal on Computing, 39(4):1581-1616, 2009. Preliminary version appeared in DNA 2004. Google Scholar
  22. Leroy G. Wade. Organic Chemistry. Prentice Hall, 2nd edition, 1991. Google Scholar
  23. Erik Winfree. Simulations of computing by self-assembly. Technical Report CaltechCSTR:1998.22, California Institute of Technology, 1998. Google Scholar
  24. Erik Winfree. Self-healing tile sets. In Junghuei Chen, Natasa Jonoska, and Grzegorz Rozenberg, editors, Nanotechnology: Science and Computation, Natural Computing Series, pages 55-78. Springer, 2006. Google Scholar
  25. Erik Winfree, Furong Liu, Lisa A. Wenzler, and Nadrian C. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, 394(6693):539-44, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact