Paper by Erik D. Demaine

Erik D. Demaine, Sarah Eisenstat, Mashhood Ishaque, and Andrew Winslow, “One-Dimensional Staged Self-Assembly”, Natural Computing, volume 12, number 2, 2013, pages 247–258.

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 steps 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) and that the problem is NP-hard. 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 20 pages.

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

Related papers:
Staged1D_DNA2011 (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.