nach oben

Natural Computing

Erschienen in:

01.03.2016

Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems

verfasst von: Andrew Winslow

Erschienen in: Natural Computing | Ausgabe 1/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We introduce a new property of tile self-assembly systems that we call size-separability. A system is size-separable if every terminal assembly is a constant factor larger than any intermediate assembly. Size-separability is motivated by the practical problem of filtering completed assemblies from a variety of incomplete “garbage” assemblies using gel electrophoresis or other mass-based filtering techniques. Here we prove that any system without cooperative bonding assembling a unique mismatch-free terminal assembly can be used to construct a size-separable system uniquely assembling the same shape. The proof achieves optimal scale factor, temperature, and tile types (within a factor of 2) for the size-separable system.

Vorheriger Artikel More on quantum, stochastic, and pseudo stochastic languages with few states

Nächster Artikel A quantum particle swarm optimization for the 0–1 generalized knapsack sharing problem

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

Otherwise \(\mathcal {S}\) has a second terminal assembly containing a tile type not found in A.

Abel Z, Benbernou N, Damian M, Demaine ED, Demaine ML, Flatland R, Kominers SD, Schweller R (2010) Shape replication through self-assembly and RNase enzymes. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1045–1064

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: STACS 2013, LIPIcs, vol. 20, pp 172–184. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik

Chen H, Doty D (2012) Parallelism and time in hierarchical self-assembly. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1163–1182

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–370CrossRefMathSciNetMATH

Doty D (2014) Producibility in hierarchical self-assembly. In: Ibarra OH, Kari L, Kopecki S (eds) Unconventional computation and natural computation, LNCS, vol 8553. Springer, Berlin Heidelberg, pp 142–154

Doty D, Patitz MJ, Reishus D, Schweller RT, Summers SM (2010) Strong fault-tolerance for self-assembly with fuzzy temperature. In: Foundations of Computer Science (FOCS), pp 417–426

Doty D, Patitz MJ, Summers SM (2009) Limitations of self-assembly at temperature 1. In: Deaton R, Suyama A (eds) DNA 15, LNCS, vol. 5877. Springer, Berlin Heidelberg, pp 35–44

Lathrop JI, Lutz JH, Patitz MJ, Summers SM (2008) Computability and complexity in self-assembly. In: Beckmann A, Dimitracopoulos C, Löwe B (eds) Logic and theory of algorithms, LNCS, vol 5028. Springer, Berlin Heidelberg, pp 349–358CrossRef

Luhrs C (2009) Polyomino-safe DNA self-assembly via block replacement. In: Goel A, Simmel FC, Sosik P (eds) DNA 14, LNCS, vol 5347. Springer, Berlin Heidelberg, pp 112–126

Luhrs C (2010) Polyomino-safe DNA self-assembly via block replacement. Nat Comput 9(1):97–109CrossRefMathSciNetMATH

Maňuch J, Stacho L, Stoll C (2010) Two lower bounds for self-assemblies at temperature 1. J Comput Biol 16(6):841–852

Meunier PE (2014) The self-assembly of paths and squares at temperature 1. Tech. rep., arxiv:1312.1299

Meunier PE, Patitz MJ, Summers SM, Theyssier G, Winslow A, Woods D (2014) Intrinsic universality in tile self-assembly requires cooperation. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 752–771

Padilla J, Patitz MJ, Pena R, Schweller RT, Seeman NC, Sheline R, Summers SM, Zhong X (2013) Asynchronous signal passing for tile self-assembly:fuel efficient computation and efficient assembly of shapes. In: Mauri G, Dennunzio A, Manzoni L, Porreca AE (eds) Unconventional computation and natural computation (UCNC), LNCS, vol 7956. Springer, Berlin Heidelberg, pp 174–185CrossRef

Reif J, Song T (2014) The computation complexity of temperature-1 tilings. Duke University, Tech. rep

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of ACM Symposium on Theory of Computing (STOC), pp 459–468

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

Summers SM (2010) Universality in algorithm self-assembly. Ph.D. thesis, Iowa State University

Winfree E (1998) Algorithmic self-assembly of DNA. Ph.D. thesis, Caltech

Winslow A (2013) Staged self-assembly and polyomino context-free grammars. In: Soloveichik D, Yurke B (eds) DNA 19, LNCS, vol 8141. Springer, Berlin Heidelberg, pp 174–188

Titel: Size-separable tile self-assembly: a tight bound for temperature-1 mismatch-free systems
verfasst von: Andrew Winslow
Publikationsdatum: 01.03.2016
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2016
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-015-9516-3

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/2016

Pseudo-inversion: closure properties and decidability

Fast arithmetic in algorithmic self-assembly

Synthetic biology of cell signaling

A quantum particle swarm optimization for the 0–1 generalized knapsack sharing problem

Doubles and negatives are positive (in self-assembly)

Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors

Premium Partner