2010/04/25 by Erik D. Demaine, Demaine, Erik D., Matthew J. Patitz +6
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced biosensing and bioanalysis techniques #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #cs.CC
paper · pdf · doi:10.48550/arxiv.1004.4383
openalex publication_date 2010/04/25 · arxiv created 2010/07/08 · arxiv updated 2010/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of DNA and RNA material) and one operation that destroys all tiles of a particular type (e.g., an RNAse enzyme destroys all RNA tiles). We show that a single use of this destruction operation enables much more efficient construction of arbitrary shapes. In particular, an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (related to the shape's Kolmogorov complexity), after scaling the shape by only a logarithmic factor. By contrast, without the destruction operation, the best such result has a scale factor at least linear in the size of the shape, and is connected only by a spanning tree of the scaled tiles. We also characterize a large collection of shapes that can be constructed efficiently without any scaling.