We analyze the number of stages, tiles, and bins needed to construct n * n squares and scaled shapes in the staged tile assembly model. In particular, we prove that there exists a staged system with b bins and t tile types assembling an n * n square using O((log n - tb - t log t)/b^2 + log log b/log t) stages and Omega((log n - tb - t log t)/b^2) are necessary for almost all n. For a shape S, we prove O((K(S) - tb - t log t)/b^2 + (log log b)/log t) stages suffice and Omega((K(S) - tb - t log t)/b^2) are necessary for the assembly of a scaled version of S, where K(S) denotes the Kolmogorov complexity of S. Similarly tight bounds are also obtained when more powerful flexible glue functions are permitted. These are the first staged results that hold for all choices of b and t and generalize prior results.The upper bound constructions use a new technique for efficiently converting each both sources of system complexity, namely the tile types and mixing graph, into a "bit string" assembly.
展开▼
机译：我们分析了在分阶段的瓷砖装配模型中构造n * n正方形和可缩放形状所需的阶段，瓷砖和箱的数量。特别地，我们证明存在一个分阶段的系统，该系统具有b个箱和t个图块类型，并使用O（（log n-tb-t log t）/ b ^ 2 + log log b / log t）阶段组装一个n * n正方形和Omega（（log n-tb-t log t）/ b ^ 2）对于几乎所有n都是必需的。对于形状S，我们证明O（（K（S）-tb-t log t）/ b ^ 2 +（log log b）/ log t）阶段就足够了，而Omega（（K（S）-tb-t log t）/ b ^ 2）对于S的缩放版本的组装是必需的，其中K（S）表示S的Kolmogorov复杂度。当允许使用更强大的灵活胶粘函数时，也将获得严格的边界。这些是第一阶段的结果，适用于b和t的所有选择并概括了先前的结果。上限构造使用一种新技术将系统复杂度的每个来源（即图块类型和混合图）有效地转换为一个“位”。字符串”程序集。
展开▼
