2026-07-22T06:30:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6377 2024-03-06T10:38:06Z ddc:004 open_access

Optimal Staged Self-Assembly of General Shapes Chalk, Cameron Martinez, Eric Schweller, Robert Vega, Luis Winslow, Andrew Wylie, Tim Tile self-assembly 2HAM aTAM DNA computing biocomputing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cameron Chalk and Eric Martinez and Robert Schweller and Luis Vega and Andrew Winslow and Tim Wylie 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.26 urn:nbn:de:0030-drops-63776 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.26 eng https://creativecommons.org/licenses/by/3.0/legalcode