Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Natural Computing
Published in: Natural Computing 1/2019

30-10-2018

Self-assembly of 4-sided fractals in the Two-Handed Tile Assembly Model

Authors: Jacob Hendricks, Joseph Opseth

Published in: Natural Computing | Issue 1/2019

Log in

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

search-config
loading …

Abstract

We consider the self-assembly of fractals in one of the most well-studied models of tile based self-assembling systems known as the Two-Handed Tile Assembly Model (2HAM). In particular, we focus our attention on a class of fractals called discrete self-similar fractals (a class of fractals that includes the discrete Sierpiński carpet). We present a 2HAM system that finitely self-assembles the discrete Sierpiński carpet with scale factor 1. Moreover, the 2HAM system that we give lends itself to being generalized and we describe how this system can be modified to obtain a 2HAM system that finitely self-assembles one of any fractal from an infinite set of fractals which we call 4-sided fractals. The 2HAM systems we give in this paper are the first examples of systems that finitely self-assemble discrete self-similar fractals at scale factor 1 in a purely growth model of self-assembly. Finally, we show that there exists a 3-sided fractal (which is not a tree fractal) that cannot be finitely self-assembled by any 2HAM system.
previous article Real-time computability of real numbers by chemical reaction networks
next article Self-assembly of shapes at constant scale using repulsive forces

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
Appendix
Available only for authorised users
Footnotes
1
Glue labels are equal and glue strengths are equal.
 
2
We are including glues with strength 0 here.
 
Literature
Abel Z, Benbernou N, Damian M, Demaine E, Demaine M, Flatland R, Kominers S, Schweller R (2010) Shape replication through self-assembly and RNase enzymes. In: SODA 2010: proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, Austin, Texas. Society for Industrial and Applied Mathematics
Barth K, Furcy D, Summers SM, Totzke P (2014) Scaled tree fractals do not strictly self-assemble. In: Unconventional computation and natural computation (UCNC) 2014, University of Western Ontario, London, Ontario, Canada, 14–18 July 2014, pp 27–39
Cannon S, Demaine ED, Demaine ML, Eisenstat S, Patitz MJ, Schweller RT, Summers SM, Winslow A (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, volume 20 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 172–184
Chalk CT, Fernandez DA, Huerta A, Maldonado MA, Schweller RT, Sweet L (2015) Strict self-assembly of fractals using multiple hands. Algorithmica 76:195–224MathSciNetMATHCrossRef
Chalk C, Demaine ED, Demaine ML, Martinez E, Schweller R, Vega L, Wylie T (2017) Universal shape replicators via self-assembly with attractive and repulsive forces. In: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms, SODA’17, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp 225–238
Cheng Q, Aggarwal G, Goldwasser MH, Kao M-Y, Schweller RT, de Espanés PM (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515MathSciNetMATHCrossRef
Cook M, Fu Y, Schweller RT (2011) Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D. In: SODA 2011: proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms. SIAM
Demaine ED, Patitz MJ, Schweller RT, Summers SM (2011) Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor (extended abstract). In: Schwentick T, Dürr C (eds) 28th international symposium on theoretical aspects of computer science (STACS 2011), vol 9. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, pp 201–212
Demaine ED, Demaine ML, Fekete SP, Patitz MJ, Schweller RT, Winslow A, Woods D (2014) One tile to rule them all: simulating any tile assembly system with a single universal tile. In: Proceedings of the 41st international colloquium on automata, languages, and programming (ICALP 2014), IT University of Copenhagen, Denmark, 8–11 July 2014, volume 857 of LNCS, pp 368–379
Demaine ED, Patitz MJ, Rogers TA, Schweller RT, Summers SM, Woods D (2016) The Two-Handed Tile Assembly Model is not intrinsically universal. Algorithmica 74(2):812–850MathSciNetMATHCrossRef
Doty D, Patitz MJ, Summers SM (2009) Limitations of self-assembly at temperature 1. In: Proceedings of the fifteenth international meeting on dna computing and molecular programming (Fayetteville, Arkansas, USA, 8–11 June 2009), pp 283–294
Doty D, Patitz MJ, Reishus D, Schweller RT, Summers SM (2010a) Strong fault-tolerance for self-assembly with fuzzy temperature. In: Proceedings of the 51st annual IEEE symposium on foundations of computer science (FOCS 2010), pp 417–426
Doty D, Kari L, Masson B (2010b) Negative interactions in irreversible self-assembly. In: DNA 16: proceedings of the sixteenth international meeting on DNA computing and molecular programming, lecture notes in computer science. Springer, pp 37–48
Doty D, Lutz JH, Patitz MJ, Schweller RT, Summers SM, Woods D (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
Fekete SP, Hendricks J, Patitz MJ, Rogers TA, Schweller RT (2015) Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly. In: Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms (SODA 2015), San Diego, CA, USA, 4–6 Jan 2015, pp 148–167
Fujibayashi K, Hariadi R, Park SH, Winfree E, Murata S (2007) Toward reliable algorithmic self-assembly of DNA tiles: a fixed-width cellular automaton pattern. Nano Lett 8(7):1791–1797CrossRef
Gilber O, Hendricks J, Patitz MJ, Rogers TA (2016) Computing in continuous space with self-assembling polygonal tiles. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms (SODA 2016), Arlington, VA, USA, 10–12 Jan 2016, pp 937–956
Hendricks J, Olsen M, Patitz MJ, Rogers TA, Thomas H (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-Universitt, Munich, Germany, 4–8 Sept, 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, 9–11 Oct, pp 800–809
Hendricks J, Patitz MJ, Rogers TA (2017b) The simulation powers and limitations of higher temperature hierarchical self-assembly systems. Fundam Inform 155(1–2):131–162MathSciNetMATHCrossRef
Hendricks J, Opseth J, Patitz MJ, Summers SM (2018) Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals. In: International conference on DNA computing and molecular programming, pp 87–104. Springer
Jonoska N, Karpenko D (2014a) Active tile self-assembly, part 1: universality at temperature 1. Int J Found Comput Sci 25(02):141–163MathSciNetMATHCrossRef
Jonoska N, Karpenko D (2014b) Active tile self-assembly, part 2: self-similar structures and structural recursion. Int J Found Comput Sci 25(02):165–194MathSciNetMATHCrossRef
Jonoska N, Karpenko D (2012) Active tile self-assembly, self-similar structures and recursion. Technical report 1211.3085, Computing Research Repository
Kao M-Y, Schweller RT (2007) Reducing tile complexity for self-assembly through temperature programming. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms (SODA 2006), Miami, Florida, Jan 2006, pp 571–580
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, 8–11 June 2009), pp 78–87
Luchsinger A, Schweller R, Wylie T (2017) Self-assembly of shapes at constant scale using repulsive forces. In: Patitz M, Stannett M (eds) Unconventional computation and natural computation - 16th international conference, UCNC 2017, Fayetteville, AR, USA, June 5–9, 2017, Proceedings, pp 82–97
Meunier P, 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, STOC 2017, Montreal, QC, Canada, 19–23 June 2017, pp 328–341
Meunier P-E, Patitz MJ, Summers SM, Theyssier G, Winslow A, Woods D (2014) Intrinsic universality in tile self-assembly requires cooperation. In: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA 2014) (Portland, OR, USA, 5–7 Jan 2014), pp 752–771
Padilla JE, Patitz MJ, Schweller RT, Seeman NC, Summers SM, Zhong X (2014) Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. Int J Found Comput Sci 25(4):459–488MathSciNetMATHCrossRef
Patitz MJ, Schweller RT, Summers SM (2011) Exact shapes and Turing universality at temperature 1 with a single negative glue. In: Proceedings of the 17th international conference on DNA computing and molecular programming, DNA’11, pp 175–189
Rothemund PW, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):2041–2053CrossRef
Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):e424CrossRef
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, Portland, Oregon, United States. ACM, pp 459–468
Summers SM (2012) Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica 63(1–2):117–136MathSciNetMATHCrossRef
Winfree E (1998) Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology
Metadata
Title
Self-assembly of 4-sided fractals in the Two-Handed Tile Assembly Model
Authors
Jacob Hendricks
Joseph Opseth
Publication date
30-10-2018
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 1/2019
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-018-9718-6

Other articles of this Issue 1/2019

Natural Computing 1/2019 Go to the issue

EditorialNotes

Preface

OriginalPaper

Self-assembly of shapes at constant scale using repulsive forces

OriginalPaper

Goal-directed navigation based on path integration and decoding of grid cells in an artificial neural network

OriginalPaper

A multi-population evolution stratagy and its application in low area/power FSM synthesis

OriginalPaper

Real-time computability of real numbers by chemical reaction networks

Erratum

Erratum to: NACO special issue editorial

Premium Partner

    Image Credits