Chen, Ho-Lin and Doty, David and Holden, Dhiraj and Thachuk, Chris and Woods, Damien and Yang, Chun-Tao (2014) Fast algorithmic self-assembly of simple shapes using random agitation. Lecture Notes in Computer Science. pp. 20-36. ISSN 0302-9743

Preview

Download (581kB) | Preview

Abstract

We study the power of uncontrolled random molecular movement in a model of self-assembly called the nubots model. The nubots model is an asynchronous nondeterministic cellular automaton augmented with rigid-body movement rules (push/pull, deterministically and programmatically applied to specific monomers) and random agitations (nondeterministically applied to every monomer and direction with equal probability all of the time). Previous work on nubots showed how to build simple shapes such as lines and squares quickly—in expected time that is merely logarithmic of their size. These results crucially make use of the programmable rigid-body movement rule: the ability for a single monomer to push or pull large objects quickly, and only at a time and place of the programmers’ choosing. However, in engineered molecular systems, molecular motion is largely uncontrolled and fundamentally random. This raises the question of whether similar results can be achieved in a more restrictive, and perhaps easier to justify, model where uncontrolled random movements, or agitations, are happening throughout the self-assembly process and are the only form of rigid-body movement. We show that this is indeed the case: we give a polylogarithmic expected time construction for squares using agitation, and a sublinear expected time construction to build a line. Such results are impossible in an agitation-free (and movement-free) setting and thus show the benefits of exploiting uncontrolled random movement.

Item Type:	Article
Keywords:	Simple Shape; Expected Time; Hexagonal Grid; Monomer State; Agitation Step;
Academic Unit:	Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	15717
Depositing User:	Damien Woods
Date Deposited:	22 Mar 2022 15:29
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer Verlag
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads