Skip to main content
SpringerLink
Log in

Strict Self-Assembly of Fractals Using Multiple Hands

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of a Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the h-handed assembly model (h-HAM), which generalizes the 2-HAM to allow up to h assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly model has yet been shown to strictly assemble an infinite fractal without significant modification to the fractal shape. In this paper we not only achieve this, but in the case of the Sierpinski carpet are able to achieve it within the 2-HAM, one of the most well studied tile assembly models in the literature. Our specific results are as follows: We provide a 6-HAM construction for a Sierpinski triangle that works at scale factor 1, 30 tile types, and assembles the fractal in a near perfect way in which all intermediate assemblies are finite-sized iterations of the recursive fractal. We further assemble a Sierpinski triangle within the 3-HAM at scale factor 3 and 990 tile types. For the Sierpinski carpet, we present a 2-HAM result that works at scale factor 3 and uses 1216 tile types. We further include analysis showing that the aTAM is incapable of strictly assembling the Sierpinski triangle considered in this paper, and that multiple hands are needed for the near-perfect assembly of a Sierpinski triangle and the Sierpinski carpet.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27

Similar content being viewed by others

References

  1. Abel, Z., Benbernou, N., Damian, M., Demaine, E.D., Demaine, M.L., Flatland, R., Kominers, S.D., Schweller, R.T.: Shape replication through self-assembly and rnase enzymes. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1045–1064 (2010)

  2. Aggarwal, G., Cheng, Q., Goldwasser, M.H., Kao, M., de Espanés, P.M., Schweller, R.T.: Complexities for generalized models of self-assembly. SIAM J. Comput. 34(6), 1493–1515 (2005). doi:10.1137/S0097539704445202

    Article  MathSciNet  MATH  Google Scholar 

  3. Barth, K., Furcy, D., Summers, S.M., Totzke, P.: Scaled tree fractals do not strictly self-assemble. In: Unconventional Computation and Natural Computation—13th International Conference, UCNC 2014, London, ON, Canada, July 14-18, 2014, Proceedings, pp. 27–39 (2014). doi:10.1007/978-3-319-08123-6_3

  4. 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: 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27–March 2, 2013, Kiel, Germany, pp. 172–184 (2013). doi:10.4230/LIPIcs.STACS.2013.172

  5. Carbone, A., Seeman, N.C.: A route to fractal dna-assembly. Nat. Comput. 1(4), 469–480 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chen, H., Doty, D.: Parallelism and time in hierarchical self-assembly. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012, pp. 1163–1182 (2012). http://portal.acm.org/citation.cfm?id=2095208&CFID=63838676&CFTOKEN=79617016

  7. Demaine, E., Patitz, M., Rogers, T., Schweller, R., Summers, S., Woods, D.: The two-handed tile assembly model is not intrinsically universal. In: Fomin, F., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 7965, pp. 400–412. Springer, Berlin (2013). doi:10.1007/978-3-642-39206-1_34

  8. Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M., Rafalin, E., Schweller, R.T., Souvaine, D.L.: Staged self-assembly: nanomanufacture of arbitrary shapes with O (1) glues. Nat. Comput. 7(3), 347–370 (2008). doi:10.1007/s11047-008-9073-0

    Article  MathSciNet  MATH  Google Scholar 

  9. Demaine, E.D., Demaine, M.L., Fekete, S.P., Patitz, M.J., Schweller, R.T., Winslow, A., Woods, D.: One tile to rule them all: simulating any tile assembly system with a single universal tile. In: Automata, Languages, and Programming—41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014, Proceedings, Part I, pp. 368–379 (2014). doi:10.1007/978-3-662-43948-7_31

  10. Demaine, E.D., Patitz, M.J., Schweller, R.T., Summers, S.M.: Self-assembly of arbitrary shapes using rnase enzymes: meeting the kolmogorov bound with small scale factor (extended abstract). In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10–12, 2011, Dortmund, Germany, pp. 201–212 (2011). doi:10.4230/LIPIcs.STACS.2011.201

  11. Doty, D.: Producibility in hierarchical self-assembly. In: Unconventional Computation and Natural Computation—13th International Conference, UCNC 2014, London, ON, Canada, July 14–18, 2014, Proceedings, pp. 142–154 (2014). doi:10.1007/978-3-319-08123-6_12

  12. Doty, D., Patitz, M.J., Reishus, D., Schweller, R.T., Summers, S.M.: Strong fault-tolerance for self-assembly with fuzzy temperature. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23–26, 2010, Las Vegas, Nevada, USA, pp. 417–426 (2010). doi:10.1109/FOCS.2010.47

  13. Fu, B., Patitz, M.J., Schweller, R.T., Sheline, R.: Self-assembly with geometric tiles. In: Automata, Languages, and Programming—39th International Colloquium, ICALP 2012, Warwick, UK, July 9–13, 2012, Proceedings, Part I, pp. 714–725 (2012). doi:10.1007/978-3-642-31594-7_60

  14. Furcy, D., Summers, S.M.: Scaled pier fractals do not strictly self-assemble. Computing Research Repository abs/1406.4197 (2014). http://arxiv.org/abs/1406.4197

  15. Kautz, S.M., Lathrop, J.I.: Self-assembly of the discrete sierpinski carpet and related fractals. In: DNA Computing and Molecular Programming, 15th International Conference, DNA 15, Fayetteville, AR, USA, June 8–11, 2009, Revised Selected Papers, pp. 78–87 (2009). doi:10.1007/978-3-642-10604-0_8

  16. Kautz, S.M., Shutters, B.: Self-assembling rulers for approximating generalized sierpinski carpets. Algorithmica 67(2), 207–233 (2013). doi:10.1007/s00453-012-9691-x

    Article  MathSciNet  MATH  Google Scholar 

  17. Lathrop, J.I., Lutz, J.H., Summers, S.M.: Strict self-assembly of discrete sierpinski triangles. Theor. Comput. Sci. 410(4–5), 384–405 (2009). doi:10.1016/j.tcs.2008.09.062

    Article  MathSciNet  MATH  Google Scholar 

  18. Lutz, J.H., Shutters, B.: Approximate self-assembly of the sierpinski triangle. Theory Comput. Syst. 51(3), 372–400 (2012). doi:10.1007/s00224-011-9345-4

    Article  MathSciNet  MATH  Google Scholar 

  19. Meunier, P., Patitz, M.J., Summers, S.M., Theyssier, G., Winslow, A., Woods, D.: Intrinsic universality in tile self-assembly requires cooperation. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5–7, 2014, pp. 752–771 (2014). doi:10.1137/1.9781611973402.56

  20. 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). doi:10.1142/S0129054114400061

    Article  MathSciNet  MATH  Google Scholar 

  21. Patitz, M.J., Summers, S.M.: Self-assembly of discrete self-similar fractals. Nat. Comput. 9(1), 135–172 (2010). doi:10.1007/s11047-009-9147-7

    Article  MathSciNet  MATH  Google Scholar 

  22. Patitz, M.J., Summers, S.M.: Self-assembly of decidable sets. Nat. Comput. 10(2), 853–877 (2011). doi:10.1007/s11047-010-9218-9

    Article  MathSciNet  MATH  Google Scholar 

  23. Rothemund, P.W., Papadakis, N., Winfree, E.: Algorithmic self-assembly of dna sierpinski triangles. PLoS Biol. 2(12), e424 (2004)

    Article  Google Scholar 

  24. Schweller, R.T., Sherman, M.: Fuel efficient computation in passive self-assembly. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6–8, 2013, pp. 1513–1525 (2013). doi:10.1137/1.9781611973105.109

  25. Wang, H.: Dominoes and the aea case of the decision problem. In: Computation, Logic, Philosophy, pp. 218–245. Springer, Berlin (1990)

  26. Winfree, E.: Algorithmic self-assembly of dna. Ph.D. thesis, California Institute of Technology (1998)

  27. Winfree, E., Bekbolatov, R.: Proofreading tile sets: error correction for algorithmic self-assembly. In: DNA Computing, 9th International Workshop on DNA Based Computers, DNA9, Madison, WI, USA, June 1–3, 2003, revised papers, pp. 126–144 (2003). doi:10.1007/978-3-540-24628-2_13

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, The University of Texas - Pan American, 1201 University Dr., Edinburg, TX, 78539, USA

    Cameron T. Chalk, Dominic A. Fernandez, Alejandro Huerta, Mario A. Maldonado, Robert T. Schweller & Leslie Sweet

Authors
  1. Cameron T. Chalk
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dominic A. Fernandez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alejandro Huerta
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mario A. Maldonado
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Robert T. Schweller
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Leslie Sweet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cameron T. Chalk.

Additional information

The authors’ research was supported in part by National Science Foundation Grant CCF-1117672.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chalk, C.T., Fernandez, D.A., Huerta, A. et al. Strict Self-Assembly of Fractals Using Multiple Hands. Algorithmica 76, 195–224 (2016). https://doi.org/10.1007/s00453-015-0022-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-015-0022-x

Keywords

Search

Navigation