Paper by Erik D. Demaine
- 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.
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.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 20, 2023 by