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

Authors Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M Summers, Andrew Winslow



PDF
Thumbnail PDF

File

LIPIcs.STACS.2013.172.pdf
  • Filesize: 0.83 MB
  • 13 pages

Document Identifiers

Author Details

Sarah Cannon
Erik D. Demaine
Martin L. Demaine
Sarah Eisenstat
Matthew J. Patitz
Robert T. Schweller
Scott M Summers
Andrew Winslow

Cite AsGet BibTex

Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M Summers, and Andrew Winslow. Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 172-184, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.172

Abstract

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.
Keywords
  • abstract tile assembly model
  • hierarchical tile assembly model
  • two-handed tile assembly model
  • algorithmic self-assembly
  • DNA computing
  • biocomputing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail