Paper by Erik D. Demaine
- Cameron Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, and Tim Wylie, “Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces”, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, January 16–19, 2017, pages 225–238.
We show how to design a universal shape replicator in a self-assembly
system with both attractive and repulsive forces. More precisely, we show
that there is a universal set of constant-size objects that, when added to
any unknown hole-free polyomino shape, produces an unbounded number of
copies of that shape (plus constant-size garbage objects). The constant-size
objects can be easily constructed from a constant number of individual tile
types using a constant number of preprocessing self-assembly steps. Our
construction uses the well-studied 2-Handed Assembly Model (2HAM) of tile
self-assembly, in the simple model where glues interact only with identical
glues, allowing glue strengths that are either positive (attractive) or
negative (repulsive), and constant temperature (required glue strength for
parts to hold together). We also require that the given shape has specified
glue types on its surface, and that the feature size (smallest distance
between nonincident edges) is bounded below by a constant. Shape replication
necessarily requires a self-assembly model where parts can both attach and
detach, and this construction is the first to do so using the natural model of
negative/repulsive glues (also studied before for other problems such as
fuel-efficient computation); previous replication constructions require more
powerful global operations such as an “enzyme” that destroys a
subset of the tile types.
- The paper is available in PDF (2901k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Replication_SODA2010 (Shape Replication Through Self-Assembly and RNase Enzymes)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 22, 2018 by