Title: Optimal Staged Self-Assembly of Linear Assemblies
Authors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
Abstract:
We analyze the complexity of building linear assemblies, sets of linear assemblies, and $\mathcal{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 \times n$ \emph{line} is $\Theta(\log_t{n} + \log_b{\frac{n}{t}} + 1)$. Generalizing to $\BO{1} \times n$ lines, we prove the minimum number of stages is $\BO{\frac{\log{n} – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}}$ and $\Omega(\frac{\log{n} – tb – t\log t}{b^2})$. We also obtain similar upper and lower bounds in a model permitting \emph{flexible glues} using non-diagonal glue functions.
Next, we consider assembling sets of lines and general shapes using $t = \BO{1}$ tile types. We prove that the minimum number of stages needed to assemble a set of $k$ lines of size at most $\BO{1} \times n$ is $\BO{\frac{k\log n}{b^2}+\frac{k\sqrt{\log n}}{b}+\log\log n}$ and $\Omega(\frac{k\log n}{b^2})$. In the case that $b = \BO{\sqrt{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 $\BO{1}$-scale using $\BO{\sqrt{k}}$ bins and optimal $\BO{\log{n}}$ stages.
Citation: Proc. of 17th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’18)
Bibtex: