Top

Natural Computing

26-04-2023

Fractal dimension of assemblies in the abstract tile assembly model

Authors: Daniel Hader, Matthew J. Patitz, Scott M. Summers

Published in: Natural Computing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we investigate the power of systems in the abstract Tile Assembly Model (aTAM) to self-assemble shapes having fractal dimensions between 1 and 2. We introduce the concept of sparsity as a tool for investigating such systems and demonstrate its utility by proving how it relates to fractal dimension. We then prove several results regarding the strict self-assembly of certain classes of fractal shapes in the aTAM including the construction of a universal tileset which, given the correct seed assembly, strictly self-assembles with nearly any desired fractal dimension. Additionally, we discuss a long standing conjecture in tile-assembly, that a class of fractals called discrete self-similar fractals cannot strictly self-assemble in the aTAM, and provide evidence that sparsity, rather than fractal dimension, is a more promising differentiating factor between shapes that can and cannot strictly self-assemble.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Here a standard counter gadget refers to commonly used log-width counter gadgets. It is unknown whether or not counter-like gadgets can be implemented in a sparse way

There are universal Turing machines which induce asymptotically smaller runtime blowups, but choosing one with a quadratic blow up makes analysis of the final fractal dimension easier.

Barth K, Furcy D, Summers SM, et al (2014) Scaled tree fractals do not strictly self-assemble. In: Unconventional Computation & Natural Computation (UCNC) 2014, University of Western Ontario, London, Ontario, Canada July 14-18, 2014, pp 27–39

Cannon S, Demaine ED, Demaine ML, et al (2013) 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. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 172–184

Cannon S, Demaine ED, Demaine ML et al (2021) On the effects of hierarchical self-assembly for reducing program-size complexity. Theor Comput Sci 894:50–78MathSciNetCrossRefMATH

Chalk CT, Fernandez DA, Huerta A et al (2015) Strict self-assembly of fractals using multiple hands. Algorithmica 76:195–224MathSciNetCrossRefMATH

Demaine ED, Patitz MJ, Rogers TA et al (2016) The two-handed tile assembly model is not intrinsically universal. Algorithmica 74(2):812–850. https://doi.org/10.1007/s00453-015-9976-yMathSciNetCrossRefMATH

Doty D, Gu X, Lutz JH, et al (2005) Zeta-Dimension. In: Proceedings of the thirtieth international symposium on mathematical foundations of computer science. Springer-Verlag, pp 283–294

Doty D, Lutz JH, Patitz MJ, et al (2012) The tile assembly model is intrinsically universal. In: Proceedings of the 53rd annual IEEE symposium on foundations of computer science, FOCS 2012, pp 302–310

Evans CG (2014) Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly. PhD thesis, California Institute of Technology

Furcy D, Summers SM (2017) Scaled pier fractals do not strictly self-assemble. Nat Comput 16(2):317–338MathSciNetCrossRefMATH

Hader D, Koch A, Patitz MJ, et al (2020) The impacts of dimensionality, diffusion, and directedness on intrinsic universality in the abstract tile assembly model. In: Chawla S (ed) Proceedings of the 2020 ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020. SIAM, pp 2607–2624

Hader D, Patitz MJ, Summers SM (2021) Fractal dimension of assemblies in the abstract tile assembly model. In: international conference on unconventional computation and natural computation, Springer, pp 116–130

Hartmanis J, Stearns RE (1965) On the computational complexity of algorithms. Trans Am Math Soc 117:285–306MathSciNetCrossRefMATH

Hendricks J, Opseth J (2017) Self-assembly of 4-sided fractals in the two-handed tile assembly model. In: Proceedings of the 16th annual confreence on unconventional computation and natural computation (UCNC 2017), Fayetteville, Arkansas, USA June 5-9, 2017, pp 113–128

Hendricks J, Olsen M, Patitz MJ, et al (2016a) Hierarchical self-assembly of fractals with signal-passing tiles (extended abstract). In: Proceedings of the 22nd international conference on dna computing and molecular programming (DNA 22), Ludwig-Maximilians-Universität, Munich, Germany September 4-8, 2016, pp 82–97

Hendricks J, Patitz MJ, Rogers TA (2016b) Universal simulation of directed systems in the abstract tile assembly model requires undirectedness. In: Proceedings of the 57th annual IEEE symposium on foundations of computer science (FOCS 2016), New Brunswick, New Jersey, USA October 9-11, 2016, pp 800–809

Hendricks J, Obseth J, Patitz MJ, et al (2018) Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals. In: Proceedings of the 24th international conference on dna computing and molecular programming (DNA 24), Shandong Normal University, Jinan, China October 8-12, pp 87–104

Jonoska N, Karpenko D (2014) Active tile self-assembly, Part 1: universality at temperature 1. Int J Found Comput Sci 25(02):141–163. https://doi.org/10.1142/S0129054114500087MathSciNetCrossRefMATH

Jonoska N, Karpenko D (2014) Active tile self-assembly, Part 2: self-similar structures and structural recursion. Int J Found Comput Sci 25(02):165–194. https://doi.org/10.1142/S0129054114500099MathSciNetCrossRefMATH

Kautz S, Shutters B (2013) Self-assembling rulers for approximating generalized sierpinski carpets. Algorithmica 67(2):207–233MathSciNetCrossRefMATH

Kautz SM, Lathrop JI (2009) Self-assembly of the Sierpinski carpet and related fractals. In: Proceedings of The fifteenth international meeting on dna computing and molecular programming (Fayetteville, Arkansas, USA, June 8-11, 2009), pp 78–87

Lathrop JI, Lutz JH, Summers SM (2009) Strict self-assembly of discrete Sierpinski triangles. Theoret Comput Sci 410:384–405MathSciNetCrossRefMATH

Lathrop JI, Lutz JH, Patitz MJ et al (2011) Computability and complexity in self-assembly. Theory Comput Syst 48(3):617–647MathSciNetCrossRefMATH

Lutz JH, Shutters B (2012) Approximate self-assembly of the sierpinski triangle. Theory Comput Syst 51(3):372–400MathSciNetCrossRefMATH

Meunier PE, Woods D (2017) The non-cooperative tile assembly model is not intrinsically universal or capable of bounded turing machine simulation. In: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing. ACM, New York, NY, USA, STOC 2017, pp 328–341, https://doi.org/10.1145/3055399.3055446,

Padilla JE, Patitz MJ, Schweller RT et al (2014) Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. Int J Found Comput Sci 25(4):459–488MathSciNetCrossRefMATH

Patitz MJ, Summers SM (2010) Self-assembly of discrete self-similar fractals. Nat Comput 1:135–172MathSciNetCrossRefMATH

Patitz MJ, Summers SM (2011) Self-assembly of decidable sets. Nat Comput 10(2):853–877MathSciNetCrossRefMATH

Patitz MJ, Summers SM (2011) Self-assembly of infinite structures: a survey. Theor Comput Sci 412(1–2):159–165. https://doi.org/10.1016/j.tcs.2010.08.015MathSciNetCrossRefMATH

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstract). In: STOC ’00: Proceedings of the thirty-second annual ACM symposium on theory of computing. ACM, Portland, Oregon, United States, pp 459–468

Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):e424CrossRef

Soloveichik D, Winfree E (2007) Complexity of self-assembled shapes. SIAM J Comput 36(6):1544–1569MathSciNetCrossRefMATH

Winfree E (1998) Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology

Woods D (2015) Intrinsic universality and the computational power of self-assembly. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 373(2046). https://doi.org/10.1098/rsta.2014.0214,

Woods D, Doty D, Myhrvold C et al (2019) Diverse and robust molecular algorithms using reprogrammable DNA self-assembly. Nature 567:366–372CrossRef

Title: Fractal dimension of assemblies in the abstract tile assembly model
Authors: Daniel Hader
Matthew J. Patitz
Scott M. Summers
Publication date: 26-04-2023
Publisher: Springer Netherlands
Published in: Natural Computing
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-023-09942-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner