Universal shape replicators via self-assembly with attractive and repulsive forces

DOI10.1137/1.9781611974782.15zbMATH1410.68122OpenAlexW2952021439MaRDI QIDQ4575751FDOQ4575751

Authors Cameron T. Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert T. Schweller, Luis Vega, Tim Wylie

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00477

Mathematics Subject Classification ID

Abstract: 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.

Recommendations

• Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles
• Self-assembly of any shape with constant tile types using high temperature
• Shape replication through self-assembly and RNase enzymes
• Smart tile self-assembly and replication

Cited in

(7)

• Self-assembly of any shape with constant tile types using high temperature
• Terminating distributed construction of shapes and patterns in a fair solution of automata
• Shape replication through self-assembly and RNase enzymes
• Covert computation in self-assembled circuits
• Covert computation in self-assembled circuits
• Smart tile self-assembly and replication
• Full tilt: universal constructors for general shapes with uniform external forces

This page was built for publication: Universal shape replicators via self-assembly with attractive and repulsive forces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575751)