Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{Staged1D_DNA2011,
  AUTHOR        = {Erik D. Demaine and Sarah Eisenstat and Mashhood Ishaque and Andrew Winslow},
  TITLE         = {One-Dimensional Staged Self-Assembly},
  BOOKTITLE     = {Proceedings of the 17th International Conference on DNA Computing and Molecular Programming (DNA 2011)},
  bookurl       = {http://dna17.caltech.edu/},
  ADDRESS       = {Pasadena, California},
  MONTH         = {September 19--23},
  YEAR          = 2011,
  PAGES         = {100--114},
  VOLUME        = 6937,
  SERIES        = {Lecture Notes in Computer Science},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-642-23638-9_10},
  dblp          = {https://dblp.org/rec/conf/dna/DemaineEIW11},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-23638-9_10">SpringerLink</A>.},
  papers        = {Staged1D_NACO},
}

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)