Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9818
• 期：1
• 页码：82-97
• 全文大小：564 KB
• 参考文献：1.Barth, K., Furcy, D., Summers, S.M., Totzke, P.: Scaled tree fractals do not strictly self-assemble. In: Ibarra, O.H., Kari, L., Kopecki, S. (eds.) UCNC 2014. LNCS, vol. 8553, pp. 27–39. Springer, Heidelberg (2014)
  2.Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat, S., Patitz, M.J., Schweller, R.T., Summers, S.M., Winslow, A.: Two hands are better than one (up to constant factors): self-assembly in the 2ham vs. atam. In: Portier, N., Wilke, T. (eds.) STACS. LIPIcs, vol. 20, pp. 172–184. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)
  3.Chalk, C.T., Fernandez, D.A., Huerta, A., Maldonado, M.A., Schweller, R.T., Sweet, L.: Strict self-assembly of fractals using multiple hands. Algorithmica, 1–30 (2015)
  4.Cheng, Q., Aggarwal, G., Goldwasser, M.H., Kao, M.-Y., Schweller, R.T., de Espanés, P.M.: Complexities for generalized models of self-assembly. SIAM J. Comput. 34, 1493–1515 (2005)MathSciNet CrossRef MATH
  5.Fochtman, T., Hendricks, J., Padilla, J.E., Patitz, M.J., Rogers, T.A.: Signal transmission across tile assemblies: 3d static tiles simulate active self-assembly by 2d signal-passing tiles. Nat. Comput. 14(2), 251–264 (2015)MathSciNet CrossRef MATH
  6.Hendricks, J., Olsen, M., Patitz, M.J., Rogers, T.A., Thomas, H.: Hierarchical self-assembly of fractals with signal-passing tiles (extended abstract). Technical Report 1606.01856, Computing Research Repository (2016)
  7.Hendricks, J., Patitz, M.J., Rogers, T.A.: Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles. In: Calude, C.S., Dinneen, M.J. (eds.) UCNC 2015. LNCS, vol. 9252, pp. 202–214. Springer, Heidelberg (2015)CrossRef
  8.Keenan, A., Schweller, R., Zhong, X.: Exponential replication of patterns in the signal tile assembly model. Nat. Comput. 14(2), 265–278 (2015)MathSciNet CrossRef MATH
  9.Lathrop, J.I., Lutz, J.H., Summers, S.M.: Strict self-assembly of discrete Sierpinski triangles. Theoret. Comput. Sci. 410, 384–405 (2009)MathSciNet CrossRef MATH
  10.Lutz, J.H., Shutters, B.: Approximate self-assembly of the sierpinski triangle. Theory Comput. Syst. 51(3), 372–400 (2012)MathSciNet CrossRef MATH
  11.Padilla, J.E., Patitz, M.J., Schweller, R.T., Seeman, N.C., Summers, S.M., Zhong, X.: Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. Int. J. Found. Comput. Sci. 25(4), 459–488 (2014)MathSciNet CrossRef MATH
  12.Padilla, J.E., Sha, R., Kristiansen, M., Chen, J., Jonoska, N., Seeman, N.C.: A signal-passing dna-strand-exchange mechanism for active self-assembly of dna nanostructures. Angewandte Chemie Int. Ed. 54(20), 5939–5942 (2015)CrossRef
  13.Patitz, M.J., Summers, S.M.: Self-assembly of discrete self-similar fractals. Nat. Comput. 1, 135–172 (2010)MathSciNet CrossRef MATH
  14.Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology, June 1998
  
• 作者单位：Jacob Hendricks (15)
  Meagan Olsen (16)
  Matthew J. Patitz (17)
  Trent A. Rogers (17)
  Hadley Thomas (16)
  
  15. Department of Computer Science and Information Systems, University of Wisconsin - River Falls, River Falls, WI, USA
  16. Fayetteville High School, Fayetteville, AR, USA
  17. Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR, USA
  
• 丛书名：DNA Computing and Molecular Programming
• ISBN：978-3-319-43994-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9818

文摘

In this extended abstract, we present high-level overviews of tile-based self-assembling systems capable of producing complex, infinite, aperiodic structures known as discrete self-similar fractals. Fractals have a variety of interesting mathematical and structural properties, and by utilizing the bottom-up growth paradigm of self-assembly to create them we not only learn important techniques for building such complex structures, we also gain insight into how similar structural complexity arises in natural self-assembling systems. Our results fundamentally leverage hierarchical assembly processes, and use as our building blocks square “tile” components which are capable of activating and deactivating their binding “glues” a constant number of times each, based only on local interactions. We provide the first constructions capable of building arbitrary discrete self-similar fractals at scale factor 1, and many at temperature 1 (i.e. “non-cooperatively”), including the Sierpinski triangle.