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
Last updated August 19, 2022 by