Physical Sciences and Mathematics Commons^™

Optimal Staged Self-Assembly Of Linear Assemblies, Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie

Computer Science Faculty Publications and Presentations

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 n line is (logt n + logb n t + 1). Generalizing to O(1) n lines, we prove the minimum number of stages is O( log n tb t log t b2 + log log b log t ) and

( log n tb t log t b2 ). Next, we consider assembling sets …