Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM

Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht

Titel: Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM

Beteiligte: Cannon, Sarah [Verfasser:in]; Demaine, Erik D. [Verfasser:in]; Demaine, Martin L. [Verfasser:in]; Eisenstat, Sarah [Verfasser:in]; Patitz, Matthew J. [Verfasser:in]; Schweller, Robert T. [Verfasser:in]; Summers, Scott M [Verfasser:in]; Winslow, Andrew [Verfasser:in]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2013

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.STACS.2013.172

Schlagwörter: hierarchical tile assembly model ; DNA computing ; two-handed tile assembly model ; abstract tile assembly model ; algorithmic self-assembly ; biocomputing

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: We study the difference between the standard seeded model (aTAM) of tile self-assembly, and the "seedless" two-handed model of tile self-assembly (2HAM). Most of our results suggest that the two-handed model is more powerful. In particular, we show how to simulate any seeded system with a two-handed system that is essentially just a constant factor larger. We exhibit finite shapes with a busy-beaver separation in the number of distinct tiles required by seeded versus two-handed, and exhibit an infinite shape that can be constructed two-handed but not seeded. Finally, we show that verifying whether a given system uniquely assembles a desired supertile is co-NP-complete in the two-handed model, while it was known to be polynomially solvable in the seeded model.

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: