Title: Optimal Staged Self-Assembly of Linear Assemblies
\nAuthors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
\nAbstract:
\nWe 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.<\/p>\n
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.<\/p>\n
Citation: Proc. of 17th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’18)
\nBibtex:<\/p>\n","protected":false},"excerpt":{"rendered":"
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 … <\/p>\n