Chen, Ho-Lin, Doty, David, Holden, Dhiraj, Thachuk, Chris, 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
DW_fast algorithmic.pdf
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 |
Related URLs: | |
URI: | https://mural.maynoothuniversity.ie/id/eprint/15717 |
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)
Downloads
Downloads per month over past year