Optimal Staged Self-Assembly of General Shapes

摘要

We analyze the number of tile types t, bins b, and stages necessary to assemble squares and scaled shapes in the staged tile assembly model. For squares, we prove stages suffice and are necessary for almost all n. For shapes S with Kolmogorov complexity K(S), we prove stages suffice and are necessary to assemble a scaled version of S, for almost all S. We obtain similarly tight bounds when the more powerful flexible glues are permitted.