Optimal staged self-assembly of linear assemblies

06.05.2019

Erschienen in:

Verfasst von: Cameron Chalk; Eric Martinez; Robert Schweller; Luis Vega; Andrew Winslow; Tim Wylie
Erschienen in: Natural Computing | Ausgabe 3/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We analyze the complexity of building linear assemblies, sets of linear assemblies, and \({\mathcal{O}}(1)\)-scale general shapes in the staged tile assembly model. For systems with at most b bins and t tile types, we prove that the minimum number of stages to uniquely assemble a \(1 \times n\)line is \(\varTheta (\log _t{n} + \log _b{\frac{n}{t}} + 1)\). Generalizing to \({\mathcal{O}}(1) \times n\) lines, we prove the minimum number of stages is \({\mathcal{O}}(\frac{\log {n} - tb - t\log t}{b^2} + \frac{\log \log b}{\log t})\) and \(\varOmega (\frac{\log {n} - tb - t\log t}{b^2})\). We also obtain similar upper and lower bounds in a model permitting flexible glues using non-diagonal glue functions. Next, we consider assembling sets of lines and general shapes using \(t = {\mathcal{O}}(1)\) tile types. We prove that the minimum number of stages needed to assemble a set of k lines of size at most \({\mathcal{O}}(1) \times n\) is \({\mathcal{O}}(\frac{k\log n}{b^2}+\frac{k\sqrt{\log n}}{b}+\log \log n)\) and \(\varOmega (\frac{k\log n}{b^2})\). In the case that \(b = \mathcal {O}(\sqrt{k})\), the minimum number of stages is \(\varTheta (\log {n})\). The upper bound in this special case is then used to assemble “hefty” shapes of at least logarithmic edge-length-to-edge-count ratio at \(\mathcal {O}(1)\)-scale using \(\mathcal {O}(\sqrt{k})\) bins and optimal \(\mathcal {O}(\log {n})\) stages.

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

Jetzt einloggen Kostenlos registrieren

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

Vorheriger Artikel The alchemy of computation: designing with the unknown

Nächster Artikel Quantum information processing in the neighborhood of a black hole

Metadaten
Fußnoten
Literatur

Titel: Optimal staged self-assembly of linear assemblies
Verfasst von: Cameron Chalk
Eric Martinez
Robert Schweller
Luis Vega
Andrew Winslow
Tim Wylie
Publikationsdatum: 06.05.2019
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2019
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-019-09740-y

Dieser Inhalt ist nur sichtbar, wenn du eingeloggt bist und die entsprechende Berechtigung hast.

Springer Professional

Optimal staged self-assembly of linear assemblies

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

Cellular automata and finite groups

UCNC 2018 special issue editorial

Preface

Correction to: Granular computing in mosaicing of images from capsule endoscopy

Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models

A universal non-conservative reversible elementary triangular partitioned cellular automaton that shows complex behavior

Premium Partner