nach oben

Natural Computing

Erschienen in:

01.03.2010

Self-assembly of discrete self-similar fractals

verfasst von: Matthew J. Patitz, Scott M. Summers

Erschienen in: Natural Computing | Ausgabe 1/2010

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we search for theoretical limitations of the Tile Assembly Model (TAM), along with techniques to work around such limitations. Specifically, we investigate the self-assembly of fractal shapes in the TAM. We prove that no self-similar fractal weakly self-assembles at temperature 1 in a locally deterministic tile assembly system, and that certain kinds of discrete self-similar fractals do not strictly self-assemble at any temperature. Additionally, we extend the fiber construction of Lathrop et al. (2009) to show that any discrete self-similar fractal belonging to a particular class of “nice” discrete self-similar fractals has a fibered version that strictly self-assembles in the TAM.

Vorheriger Artikel Robust self-assembly of graphs

Nächster Artikel Operon structure optimization by random self-assembly

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Adleman LM, Cheng Q, Goel A, Huang M-D, Kempe D, de Espanés PM, Rothemund PWK (2002) Combinatorial optimization problems in self-assembly. In: Proceedings of the thirty-fourth annual ACM symposium on theory of computing, pp 23–32

Adleman LM, Kari J, Kari L, Reishus D (2002) On the decidability of self-assembly of infinite ribbons. In: Proceedings of the 43rd annual IEEE symposium on foundations of computer science, pp 530–537

Aggarwal G, Goldwasser MH, Kau M-Y, Schweller RT (2004) Complexities for generalized models of self-assembly. In: Proceedings of ACM-SIAM symposium on discrete algorithms

Doty D, Gu X, Lutz JH, Mayordomo E, Moser P (2005) Zeta-dimension. In: Proceedings of the thirtieth international symposium on mathematical foundations of computer science, Springer-Verlag, NY, pp 283–294

Graham RL, Knuth DE, Patashnik O (1994) Concrete mathematics. Addison-Wesley, Reading

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

Kao M-Y, Schweller RT (2008) Randomized self-assembly for approximate shapes, International Colloqium on Automata, Languages, and Programming (ICALP) In: Aceto L, Damgård I, Goldberg LA, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I (eds) Lecture notes in computer science, vol 5125. Springer, Berlin, pp 370–384

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 (to appear)

Lathrop JI, Lutz JH, Patitz Matthew J, Summers SM (2008) Computability and complexity in self-assembly. In: Proceedings of the fourth conference on computability in Europe Athens, Greece, 15–20 June 2008

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

Majumder U, LaBean TH, and Reif JH (2007) Activatable tiles for compact error-resilient directional assembly. In: Thirteenth international meeting on DNA computing (DNA 13), Memphis, Tennessee, 4–8 June 2007

Rothemund PWK (2001) Theory and experiments in algorithmic self-assembly. Ph.D. thesis, University of Southern California, December

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

Seeman NC (1982) Nucleic-acid junctions and lattices. J Theor Biol 99:237–247CrossRef

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

Wang H (1961) Proving theorems by pattern recognition—II. Bell Syst Tech J XL(1):1–41

Wang H (1963) Dominoes and the AEA case of the decision problem. In: Proceedings of the symposium on mathematical theory of automata, New York, 1962, Polytechnic Press of Polytechnic Institute of Brooklyn, Brooklyn, NY, pp 23–55

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

Titel: Self-assembly of discrete self-similar fractals
verfasst von: Matthew J. Patitz
Scott M. Summers
Publikationsdatum: 01.03.2010
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2010
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-009-9147-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2010

Foreword

Hybrid Functional Petri Nets as MP systems

Modelling programmed frameshifting with frameshift machines

Polyomino-safe DNA self-assembly via block replacement

Robust self-assembly of graphs

Isothermal reactivating Whiplash PCR for locally programmable molecular computation

Premium Partner