nach oben

Natural Computing

Erschienen in:

01.09.2012

Step-wise tile assembly with a constant number of tile types

verfasst von: Ján Maňuch, Ladislav Stacho, Christine Stoll

Erschienen in: Natural Computing | Ausgabe 3/2012

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 study the step-wise tile assembly model introduced by Reif (in: Based computers III, vol 48 of DIMACS, 1999) in which shape is assembled in multiple steps. In each step the partially built structure is exposed to a new set of tiles. We show that an N × N square can be assembled in N steps using a constant number of tile types. In general, we show that a constant number of tile types (24) is sufficient to assemble a large class of shapes in n steps, where n is the number of tiles of the shape. This class includes all shapes obtained from any shape by scaling by a factor of 2, in which case only 14 tile types suffices. For general shapes, we show that the tile complexity of this model is related to the monotone connected node search number of a spanning tree of the shape assuming the number of steps is n.

Vorheriger Artikel Parallel predator–prey interaction for evolutionary multi-objective optimization

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

After personal communication with the authors of Demaine et al. (2008) we were advised that original bound of 16 in the paper should be 52.

Abelson H, Allen D, Coore D, Hanson C, Homsy G, Knight TF, Nagpal R, Rauch E, Sussman GJ, Weiss R (2000) Amorphous computing. Commun ACM 43:74–82CrossRef

Adleman L, Cheng Q, Goel A, Huang M-D, Kempe D, de Espanes PM, Rothemund P (2002) Combinatorial optimization problems in self-assembly. In: Proceedings of STOC, Montreal, Canada, pp 23–32

Aggarwal G, Cheng Q, Goldwasser MH, Kao M-Y, Espanes PM, Schweller RT (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34(6):1493–1515MathSciNetMATHCrossRef

Barriere L, Fraigniaud P, Santoro N, Thilikos DM (2003) Connected and internal graph searching. In: 29th workshop on graph theoretic concepts in computer science (WG). LNCS, vol 2880. Springer, Heidelberg, pp 34–45

Best MJ A bound on connected pathwidth. Manuscript

Demaine ED, Demaine ML, Fekete SP, Ishaque M, Rafalin E, Schweller RT, Souvaine DL (2008) Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Nat Comput 7(3):347–370MathSciNetMATHCrossRef

Fraigniaud P, Nisse N (2008) Monotony properties of connected visible graph searching. Inf Comput 206(12):1383–1393MathSciNetMATHCrossRef

Gomez-Lopez M, Preece J, Stoddart J (1996) The art and science of self-assembling molecular machines. Nanotechnology 7:183–192CrossRef

Kirousis LM, Papadimitriou CH (1985) Interval graphs and searching. Discr Math 55(1):181–184MathSciNetMATHCrossRef

Kirousis L, Papadimitriou C (1986) Searching and pebbling. Theor Comput Sci 47(2):205–218MathSciNetMATHCrossRef

LaBean T, Yan H, Kopatsch J, Liu F, Winfree E, Reif JH, Seeman N (2000) Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes. J Am Chem Soc 122:1848–1860CrossRef

Maňuch J, Stacho L, Stoll C (2009) Step-assembly with a constant number of tile types. In: Proceedings of the 20th international symposium on algorithms and computation (ISAAC, Hawaii, 2009), number 5878 in LNCS, pp 954–963

Mao C, LaBean TH, Reif J, Seeman N (2000) Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature 407:493–496CrossRef

Reif JH (1999) Local parallel biomolecular computing. In: DNA based computers III, vol 48 of DIMACS. American Mathematical Society, Providence, pp 217–254

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares. In: Proceedings of STOC, New York, pp 459–468

Rothemund P, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2:2041–2053CrossRef

Seeman N (1998) DNA nanotechnology: novel DNA constructions. Annu Rev Biophys Biomol Struct 27:225–248CrossRef

Summers SM (2012) Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica 63(1–2):117–136

Winfree E, Yang X, Seeman N (1996) Universal computation via self-assembly of DNA: some theory and experiments. In: Proceedings of the second annual meeting on DNA based computers, pp 191–214

Winfree E, Liu F, Wenzler LA, Seeman NC (1998) Design and self-assembly of two dimensional DNA crystals. Nature 394:539–544CrossRef

Titel: Step-wise tile assembly with a constant number of tile types
verfasst von: Ján Maňuch
Ladislav Stacho
Christine Stoll
Publikationsdatum: 01.09.2012
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2012
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-012-9321-1

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 3/2012

Using enzymatic numerical P systems for modeling mobile robot controllers

Degeneracy and networked buffering: principles for supporting emergent evolvability in agile manufacturing systems

Designing a new software tool for Digital Imagery based on P systems

To boldly go: an occam-π mission to engineer emergence

Stateless multicounter 5′ → 3′ Watson–Crick automata: the deterministic case

Comparing simulation algorithms for multienvironment probabilistic P systems over a standard virtual ecosystem