License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.26
URN: urn:nbn:de:0030-drops-63776
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6377/
Go to the corresponding LIPIcs Volume Portal

Chalk, Cameron ; Martinez, Eric ; Schweller, Robert ; Vega, Luis ; Winslow, Andrew ; Wylie, Tim

Optimal Staged Self-Assembly of General Shapes

pdf-format:
LIPIcs-ESA-2016-26.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chalk_et_al:LIPIcs:2016:6377,
  author =	{Cameron Chalk and Eric Martinez and Robert Schweller and Luis Vega and Andrew Winslow and Tim Wylie},
  title =	{{Optimal Staged Self-Assembly of General Shapes}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6377},
  URN =		{urn:nbn:de:0030-drops-63776},
  doi =		{10.4230/LIPIcs.ESA.2016.26},
  annote =	{Keywords: Tile self-assembly, 2HAM, aTAM, DNA computing, biocomputing}
}

Keywords: Tile self-assembly, 2HAM, aTAM, DNA computing, biocomputing
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI