Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Natural Computing
Erschienen in: Natural Computing 1/2019

01.08.2018

Verification in staged tile self-assembly

verfasst von: Robert Schweller, Andrew Winslow, Tim Wylie

Erschienen in: Natural Computing | Ausgabe 1/2019

Einloggen

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

search-config
loading …

Abstract

We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are \(\textsf {coNP}^{\textsf {NP}}\)-hard and contained in PSPACE (and in \(\mathrm {\Pi }^\textsf {P}_{2s}\) for staged systems with s stages). En route, we prove that unique shape verification problem in the 2HAM is \(\textsf {coNP}^{\textsf {NP}}\)-complete.
Vorheriger Artikel Self-assembly of shapes at constant scale using repulsive forces
Nächster Artikel Computing with chemical reaction networks: a tutorial

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
Fußnoten
1
The original staged model (Demaine et al. 2008) only considered O(1) distinct tile types, and thus for simplicity allowed tiles to be added at any stage (since \(\mathcal {O}(1)\) extra bins could hold the individual tile types to mix at any stage). Because systems here may have super-constant tile complexity, we restrict tiles to only be added at the initial stage.
 
2
This is a slight modification of the original staged model (Demaine et al. 2008) in that there is no requirement of a final stage with a single output bin. This may be a slightly more capable model, and so it is considered here. However, all results in this paper apply to both variants of the model.
 
Literatur
Adleman LM, Cheng Q, Goel A, Huang MDA, 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
Bryans N, Chiniforooshan E, Doty D, Kari L, Seki S (2013) The power of nondeterminism in self-assembly. Theory Comput 9(1):1–29MathSciNetCrossRefMATH
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. Schloss Dagstuhl, pp 172–184
Chalk C, Martinez E, Schweller R, Vega L, Winslow A, Wylie T (2016) Optimal staged self-assembly of general shapes. In: Proceedings of the 24th European symposium of algorithms, LIPIcs, vol 57. Schloss Dagstuhl, pp 26:1–26:17
Chalk C, Schweller R, Winslow A, Wylie T (2017) Too hot 2HAMdle: high-temperature two-handed self-assembly. Under submission
Cheng Q, Aggarwal G, Goldwasser MH, Kao MY, Schweller RT, de Espanés PM (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515MathSciNetCrossRefMATH
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–370MathSciNetCrossRefMATH
Demaine ED, Eisenstat S, Ishaque M, Winslow A (2011) One-dimensional staged self-assembly. In: Proceedings of the 17th international conference on DNA computing and molecular programming, DNA’11, pp 100–114
Demaine ED, Fekete SP, Scheffer C, Schmidt A (2015) New geometric algorithms for fully connected staged self-assembly. In: DNA computing and molecular programming, LNCS, vol 9211. Springer, pp 104–116
Doty D (2014) Producibility in hierarchical self-assembly. In: Proceedings of unconventional computation and natural computation (UCNC), LNCS, vol 8553. Springer, pp 142–154
Lagoudakis MG, Labean TH (1999) 2d dna self-assembly for satisfiability. In: 5th international meeting on DNA based computers
Schaefer M, Umans C (2002) Completeness in the polynomial-time hierarchy: a compendium. SIGACT News 33(3):32–49CrossRef
Metadaten
Titel
Verification in staged tile self-assembly
verfasst von
Robert Schweller
Andrew Winslow
Tim Wylie
Publikationsdatum
01.08.2018
Verlag
Springer Netherlands
Erschienen in
Natural Computing / Ausgabe 1/2019
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-018-9701-2

Weitere Artikel der Ausgabe 1/2019

Natural Computing 1/2019 Zur Ausgabe

OriginalPaper

Particle computation: complexity, algorithms, and logic

OriginalPaper

Evolving the process of a virtual composer

EditorialNotes

Preface

EditorialNotes

NACO special issue editorial

OriginalPaper

Computing with chemical reaction networks: a tutorial

OriginalPaper

Self-assembly of shapes at constant scale using repulsive forces

Premium Partner

    Bildnachweise