MURAL - Maynooth University Research Archive Library



    Fast algorithmic self-assembly of simple shapes using random agitation


    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

    [thumbnail of DW_fast algorithmic.pdf]
    Preview
    Text
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads