Paper by Erik D. Demaine

Reference:

Zachary Abel, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Flatland, Scott Kominers, and Robert Schweller, “Shape Replication Through Self-Assembly and RNase Enzymes”, in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, January 17–19, 2010, pages 1045–1064.

BibTeX

@InProceedings{Replication_SODA2010,
  AUTHOR        = {Zachary Abel and Nadia Benbernou and Mirela Damian and
                   Erik D. Demaine and Martin L. Demaine and Robin Flatland and
                   Scott Kominers and Robert Schweller},
  TITLE         = {Shape Replication Through Self-Assembly and {RNase} Enzymes},
  BOOKTITLE     = {Proceedings of the 21st Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2010)},
  bookurl       = {http://www.siam.org/meetings/da10/},
  ADDRESS       = {Austin, Texas},
  MONTH         = {January 17--19},
  YEAR          = 2010,
  PAGES         = {1045--1064},

  withstudent   = 1,
  papers        = {NegativeReplication_SODA2017},
  doi           = {https://dx.doi.org/10.1137/1.9781611973075.85},
  dblp          = {https://dblp.org/rec/conf/soda/AbelBDDDFKS10},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1137/1.9781611973075.85">SIAM</A>.},
}

Abstract:

We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only O(1) distinct tile types and O(1) stages. Further, we show how to replicate precisely n copies of a shape using O(log n) stages and O(1) tile types.

Comments:

This paper is also available from SIAM.

Availability:

The paper is available in PDF (1398k).

See information on file formats.

[Google Scholar search]

Related papers:

NegativeReplication_SODA2017 (Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces)