Dabby, Nadine and Chen, Ho-Lin
(2013)
*Active Self-Assembly of Simple Units Using an Insertion Primitive.*
In:
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.
SIAM
, Philadelphia, PA, pp. 1526-1536.
ISBN 978-1-61197-251-1.
http://resolver.caltech.edu/CaltechAUTHORS:20161005-163012754

PDF
- Published Version
See Usage Policy. 226Kb |

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20161005-163012754

## Abstract

While computer science has given us a framework for determining the complexity and difficulty of solving computational problems, we do not yet have a theoretical framework for knowing what actions, behaviors, and life-like qualities can emerge from a given set of simple modular units. There has been much interest in developing models for programming active self-assembly processes in both the reconfigurable robotics community and the nanotechnology community. With respect to materials science and nanotechnology, the models proposed to date are either not yet implementable with our current understanding of synthetic chemistry or those that are implementable are limited to a set of features that do not capture the power of active components. Prior implementable models of molecular assembly only considered the passive behaviors of attaching and detaching from a complex. Inspired by the algorithmic tile assembly model [Winfree, 1996] and the graph grammar assembly model [Klavins et al., 2004], we describe a formal model for studying the complexity of self-assembled structures with active molecular components. In particular, we add an insertion primitive and we show a direct mapping of our model to a molecular implementation using DNA. We show that the expressive power of this language is stronger than regular languages, but at most as strong as context free grammars. Here, we explore the trade-off between the complexity of the system (in terms of the number of unit types), and the behavior of the system and speed of its assembly. We find that we can grow a line of any given length n in expected time O(log^3 n) using O(log^2 n) monomers. If we grow a line with k insertion rules, either the expected final length is infinite or the expected length at time t is at most (2t+2)^k^2, which is polynomial in t.

Item Type: | Book Section | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||||

Additional Information: | © 2013 SIAM. Research supported by an NSF Graduate Research Fellowship, NSF grant CCF-0829805, and the Molecular Programming Project under NSF grant 0832824. Research supported by NSC grant number 101-2218-E-002-007-, National Taiwan University Electrical Engineering Department, NSF grant CCF-0829805, the Molecular Programming Project under NSF grant CCF-0832824, and the Caltech Center for the Mathematics of Information (CMI). | ||||||||||||

Funders: |
| ||||||||||||

Record Number: | CaltechAUTHORS:20161005-163012754 | ||||||||||||

Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20161005-163012754 | ||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||

ID Code: | 70904 | ||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||

Deposited By: | Kristin Buxton | ||||||||||||

Deposited On: | 05 Oct 2016 23:44 | ||||||||||||

Last Modified: | 05 Oct 2016 23:44 |

Repository Staff Only: item control page