Back to Search Start Over

One-dimensional staged self-assembly.

One-dimensional staged self-assembly.

Authors :
Demaine, Erik
Eisenstat, Sarah
Ishaque, Mashhood
Winslow, Andrew
Source :
Natural Computing. Jun2013, Vol. 12 Issue 2, p247-258. 12p.
Publication Year :
2013

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 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 $$\Omega(\sqrt{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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
15677818
Volume :
12
Issue :
2
Database :
Academic Search Index
Journal :
Natural Computing
Publication Type :
Academic Journal
Accession number :
87785424
Full Text :
https://doi.org/10.1007/s11047-012-9359-0