Fast algorithmic self-assembly of simple shapes using random agitation

DOI10.1007/978-3-319-11295-4_2MaRDI QIDQ2921470zbMATH OpenOpenAlexFDO

Authors Ho-Lin Chen, David Doty, Dhiraj Holden, Chris Thachuk, Damien Woods, Chun-Tao Yang

Publication date 8 October 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4828

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Abstract: We study the power of uncontrolled random molecular movement in the nubot model of self-assembly. The nubot 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 the nubot model 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 control the movement of a 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.

Recommendations

• Parallel Computation Using Active Self-assembly
• Parallel computation using active self-assembly
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Randomized self-assembly for exact shapes
• A minimal requirement for self-assembly of lines in polylogarithmic time

Cited in

(8)

• A minimal requirement for self-assembly of lines in polylogarithmic time
• Non-determinism reduces construction time in active self-assembly using an insertion primitive
• Leader election and shape formation with self-organizing programmable matter
• Randomized Self Assembly of Rectangular Nano Structures
• Improved Leader Election for Self-organizing Programmable Matter
• Active Self-Assembly of Simple Units Using an Insertion Primitive
• A minimal requirement for self-assembly of lines in polylogarithmic time
• Turning machines

This page was built for publication: Fast algorithmic self-assembly of simple shapes using random agitation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921470)