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
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
- 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
Last updated January 15, 2021 by