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.

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.

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)