Paper by Erik D. Demaine

Erik D. Demaine, Sarah Eisenstat, Mashhood Ishaque, and Andrew Winslow, “One-Dimensional Staged Self-Assembly”, in Proceedings of the 17th International Conference on DNA Computing and Molecular Programming (DNA 2011), Lecture Notes in Computer Science, volume 6937, Pasadena, California, September 19–23, 2011, pages 100–114.

We introduce the problem of staged self-assembly of one-dimensional nanostructures, which becomes interesting when the elements are labeled (e.g., representing functional units that must be placed at specific locations). In a restricted model in which each operation has a single terminal assembly, we prove that assembling a given string of labels with the fewest stages is equivalent, up to constant factors, to compressing the string to be uniquely derived from the smallest possible context-free grammar (a well-studied O(log n)-approximable problem). Without this restriction, we show that the optimal assembly can be substantially smaller than the optimal context-free grammar, by a factor of Ω(√n/log n) even for binary strings of length n. Fortunately, we can bound this separation in model power by a quadratic function in the number of distinct glues or tiles allowed in the assembly, which is typically small in practice.

This paper is also available from SpringerLink.

The paper is available in PostScript (525k), gzipped PostScript (247k), and PDF (232k).
See information on file formats.
[Google Scholar search]

Related papers:
Staged1D_NACO (One-Dimensional Staged Self-Assembly)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.