Paper by Erik D. Demaine
- Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine, “Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues”, Natural Computing, volume 7, number 3, September 2008, pages 347–370. Special issue of selected papers from the 13th International Meeting on DNA Computing, 2007.
We introduce staged self-assembly of Wang tiles, where tiles can be
added dynamically in sequence and where intermediate constructions can be
stored for later mixing. This model and its various constraints and
performance measures are motivated by a practical nanofabrication scenario
through protein-based bioengineering. Staging allows us to break through the
traditional lower bounds in tile self-assembly by encoding the shape in the
staging algorithm instead of the tiles. All of our results are based on the
practical assumption that only a constant number of glues, and thus only a
constant number of tiles, can be engineered. Under this assumption,
traditional tile self-assembly cannot even manufacture an
n × n square; in contrast, we show how staged
assembly in theory enables manufacture of arbitrary shapes in a variety of
precise formulations of the model.
- This paper is also available from SpringerLink.
- The tile bound of 16 in Table 1 row 5 (arbitrary shape) and in Theorem 5 is incorrect; the correct bound (for the same algorithm) is 52.
- The paper is available in PDF (1968k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- StagedAssembly_DNA2007 (Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by