**Reference**:- 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. **Abstract**:-
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. **Comments**:- This paper is also available from SpringerLink.
**Availability**:- 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.

Last updated July 7, 2020 by Erik Demaine.