2013/04/29 by David Doty, Doty, David · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced biosensing and bioanalysis techniques #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #cs.CC #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1304.7804
openalex publication_date 2013/04/29 · arxiv created 2013/05/01 · arxiv updated 2013/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Three results are shown on producibility in the hierarchical model of tile self-assembly. It is shown that a simple greedy polynomial-time strategy decides whether an assembly A is producible. The algorithm can be optimized to use O(|A| log2 |A|) time. Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow showed that the problem of deciding if an assembly A is the unique producible terminal assembly of a tile system T can be solved in O(|A|2 |T| + |A| |T|2) time for the special case of noncooperative "temperature 1" systems. It is shown that this can be improved to O(|A| |T| log |T|) time. Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently -- i.e., if the positions that they share have the same tile type in each assembly -- then their union is also producible.