Optimal staged self-assembly of linear assemblies

摘要

We analyze the complexity of building linear assemblies, sets of linear assemblies, and O(1)-scale general shapes in the staged tile assembly model. For systems with at most b bins and t tile types, we prove that the minimum number of stages to uniquely assemble a 1 X n line is Theta(log(t) n + logb n/t + 1). Generalizing to O(1) X n lines, we prove the minimum number of stages is O(log n tb t log t/b(2) + log log b/log t) and Omega(log n tb t log t/b(2)). We also obtain similar upper and lower bounds in a model permitting flexible glues using non-diagonal glue functions. Next, we consider assembling sets of lines and general shapes using t = O(1) tile types. We prove that the minimum number of stages needed to assemble a set of k lines of size at most O(1) X n is O(k log n/b(2) + k root log n/b + log log n) and Omega(k log n/b(2)). In the case that b = O(root k), the minimum number of stages is Theta(log n). The upper bound in this special case is then used to assemble "hefty" shapes of at least logarithmic edge-length-to-edge-count ratio at O(1)-scale using O(root k) bins and optimal O(log n) stages.