Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

15.03.2021 | Ausgabe 2/2021

Natural Computing 2/2021

Geometric tiles and powers and limitations of geometric hindrance in self-assembly

Zeitschrift:
Natural Computing > Ausgabe 2/2021
Autoren:
Daniel Hader, Matthew J. Patitz
Wichtige Hinweise
D. Hader, M. J. Patitz: This author’s research was supported in part by National Science Foundation Grant CCF-1422152 and CAREER-1553166.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

Tile-based self-assembly systems are capable of universal computation and algorithmically directed growth. Systems capable of such behaviors typically make use of “glue cooperation” in which the glues on at least 2 sides of a tile must match and bind to those exposed on the perimeter of an assembly for that tile to attach. However, several models have been developed which utilize “weak cooperation”, where only a single glue needs to bind but other preventative forces (such as geometric, or steric, hindrance) provide additional selection for which tiles may attach, and where this allows for algorithmic behavior. In this paper we first work in a model where tiles are allowed to have geometric bumps and dents on their edges. We show how such “geometric” tiles can simulate systems of square tiles with complex glue functions (using asymptotically optimal sizes of bumps and dents). We then show that at scale factor 1 it is impossible for geometric tiles to simulate the behavior of systems which can include duples (i.e. tiles either twice as long or twice as tall as square tiles), and also that with only weak cooperation via geometric hindrance, no system in any model can simulate even a class of tightly constrained, deterministic cooperative systems. This helps to further define the limits of the powers of systems relying on geometric hindrance instead of glue cooperation.A shortened version of this paper appeared in the proceedings of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019).

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2021

Natural Computing 2/2021 Zur Ausgabe

EditorialNotes

Preface

Premium Partner