# Two-Handed Assembly Model (2HAM)

The 2HAM ^{[1]} ^{[2]} is a generalization of the aTAM meant to model systems where self-assembly of multiple sub-assemblies can occur separately and in parallel, and then those sub-assemblies can combine with each other. The "2-handed" portion of the name comes from the fact that each combination is of exactly two assemblies at a time. Note that variations of this model have appeared in several papers and by several different names (e.g. hierarchical self-assembly, polyominoes, etc.) ^{[3]}^{[4]}^{[1]}^{[5]}^{[6]}^{[7]}.

## Contents |

## Informal Description of the Model

The 2HAM is formulated without a seed assembly structure, so that all individual tiles have equal status in the initial solution, and assembly begins as separate assemblies nucleate in parallel. Each step of assembly occurs as any two existing assemblies (which at first are just the singleton tiles) which are able to bind to each other, with strength at least equal to the temperature parameter and without any overlaps, combine to form a new assembly. Since it is experimentally challenging to enforce the seeded nature of growth in the aTAM (see kTAM), the 2HAM provides a perhaps more experimentally feasible model in that respect, by removing the seed constraint. However, since the 2HAM allows for pairs of arbitrarily large assemblies to combine with each other as long as there are no overlaps of any portions of those assemblies in the final configuration, two new difficulties arise in terms of experimental viability. First, the rate of diffusion of assemblies will decrease as their sizes increase, making it less and less likely for combinations of larger assemblies to occur. Second, in order to enforce the requirement that pairs of assemblies can only join in configurations in which they don't contain overlaps, it would need to be the case that assemblies are completely rigid (which is certainly not the case with DNA implementations of tiles) so that portions of the assemblies couldn't bend to avoid the overlaps. The fact that the 2HAM allows for the combination of arbitrarily large assemblies gives rise to the phenomenon that, although all interactions are local in the context of being between exactly two assemblies which are immediately adjacent to each other, there is also a notion of instantaneous long range interactions on the scale of individual tiles. This is because the existence of a tile at a location arbitrarily far from another can dictate whether or not that tile will be able to bind to a tile in another assembly by perhaps providing enough cooperative binding, or instead perhaps by blocking the assemblies from achieving a binding configuration. This long range interaction provides for a great amount of difference in the power of the 2HAM versus the aTAM, and is also the reason that the 2HAM isn't immediately similar to ACA systems (see Wang tiling vs. the aTAM).

## Formal model definition

Two assemblies and are *disjoint* if
For two assemblies and , define the *union* to be the assembly defined for all by if is defined, and otherwise. Say that this union is *disjoint* if and are disjoint.

The *binding graph* of an assembly is the grid graph
, where , and if and only if (1)
, (2)
, and (3)
.
Given , an
assembly is -stable (or simply stable if is understood from context), if it
cannot be broken up into smaller assemblies without breaking bonds
of total strength at least ; i.e., if every cut of
has weight at least , where the weight of an edge is the strength of the glue it represents. In contrast to the model of Wang tiling, the nonnegativity of the strength function implies that glue mismatches between adjacent tiles do not prevent a tile from binding to an assembly, so long as sufficient binding strength is received from the (other) sides of the tile at which the glues match.

For assemblies and , we write to denote the assembly defined for all by , and write if there exists such that ; i.e., if is a translation of .
Define the supertile of to be the set .
A supertile is *-stable* (or simply stable) if all of the assemblies it contains are -stable; equivalently, is stable if it contains a stable assembly, since translation preserves the property of stability. Note also that the notation is the size of the super tile (i.e., number of tiles in the supertile) is well-defined, since translation preserves cardinality (and note in particular that even though we define as a set, does not denote the cardinality of this set, which is always ).

For two supertiles and , and temperature , define the *combination* set to be the set of all supertiles such that there exist and such that (1) and are disjoint (steric protection), (2) is -stable, and (3) . That is, is the set of all -stable supertiles that can be obtained by attaching to stably, with if there is more than one position at which could attach stably to .

It is common with seeded assembly to stipulate an infinite number of copies of each tile, but our definition allows for a finite number of tiles as well. Our definition also allows for the growth of infinite assemblies and finite assemblies to be captured by a single definition, similar to the definitions of ^{[8]} for seeded assembly.

Given a set of tiles , define a *state* of to be a multiset of supertiles, or equivalently, is a function mapping supertiles of to , indicating the multiplicity of each supertile in the state. We therefore write if and only if .

A *(two-handed) tile assembly system* (*TAS*) is an ordered triple , where is a finite set of tile types, is the *initial state*, and is the temperature. If not stated otherwise, assume that the initial state is defined for all such that , and for all other supertiles . That is, is the state consisting of a countably infinite number of copies of each individual tile type from , and no other supertiles. In such a case we write to indicate that uses the default initial state.

Given a TAS , define an *assembly sequence* of to be a sequence of states (where if is an infinite assembly sequence), and is constrained based on in the following way: There exist supertiles such that (1) , (2) ,with the convention that (3) if , then , , otherwise if , then , and (4) for all .
That is, is obtained from by picking two supertiles from that can attach to each other, and attaching them, thereby decreasing the count of the two reactant supertiles and increasing the count of the product supertile. If , we say that is *nascent*.

Unlike the seeded model, an infinite assembly sequence in the two-handed model may not have a unique limit state. For example, consider an assembly sequence that starts from an infinite number of single tiles, then continually creates a size-2 supertile from tiles before attaching to a larger and ever-growing supertile. The count of forever oscillates between 0 and 1, so there is no limit state, although the larger supertile, which is more precisely a sequence of supertiles, will have a well-defined limit.

Given an assembly sequence of and a supertile for some , define the *predecessors* of in to be the multiset if and and attached to create at step of the assembly sequence, and define otherwise. Define the *successor* of in to be is a predecessor of in , and define otherwise. A sequence of supertiles is a *supertile assembly sequence* of if there is an assembly sequence of such that, for all , , and is *nascent* if is nascent.

The *result* of a supertile assembly sequence is the unique supertile such that there exist an assembly and, for each , assemblies such that and, for each , . For all supertiles , we write (or when is clear from context) to denote that there is a supertile assembly sequence such that and . It can be shown using the techniques of ^{[9]} for seeded systems that for all two-handed tile assembly systems supplying an infinite number of each tile type, is a transitive, reflexive relation on supertiles of . We write () to denote an assembly sequence of length 1 from to and () to denote an assembly sequence of length 1 from to if , and otherwise (i.e. ) an assembly sequence of length 0.

A supertile is *producible*, and we write , if it is the result of a nascent supertile assembly sequence. A supertile is *terminal* if, for all producible supertiles , . Note that a supertile could be non-terminal in the sense that there is a producible supertile such that , yet it may not be possible to produce and simultaneously if some tile types are given finite initial counts, implying that cannot be "grown" despite being non-terminal. If the count of each tile type in the initial state is , then all producible supertiles are producible from any state, and the concept of terminal becomes synonymous with "not able to grow", since it would always be possible to use the abundant supply of tiles to assemble alongside and then attach them.} Define to be the set of terminal and producible supertiles of . is directed (a.k.a., *deterministic*, *confluent*) if .

Let be a shape. We say *self-assembles* in if, for each , there exists such that ; i.e., uniquely assembles into the shape .

## Example

In this section we provide an example of a simple 2HAM system and show exactly what assemblies are producible within it in order to help clarify the ways in which assemblies are produced within the model.

Let be a 2HAM system where is defined as the tile types in Figure 1. Figures 1-5 show the complete set of 29 supertiles which make up , and Figure 5 shows the single member of . The producible supertiles are broken into groups to show the earliest step of combinations during which they can appear, although for some there are multiple paths of combinations which can form them. (We don't show duplicate copies.) Furthermore, recall from the definition of the model that all producible supertiles are available at every step, so for example a supertile produced in step 2 may combine with one produced in step 1 to create a new supertile in step 3. Also note that the use of "steps" is merely a convenience for discussing this example, but typically the sets and are simply defined as those supertiles producible in the limit.In this section we provide an example of a simple 2HAM system and show exactly what assemblies are producible within it in order to help clarify the ways in which assemblies are produced within the model.

## 2HAM Results

Intrinsic Universality in the 2HAM

Impossibility and Efficiency Comparisions Between aTAM and 2HAM

Fuzzy Temperature Fault Tolerance

## References

- ↑
^{1.0}^{1.1}*Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Pablo Moisset de Espanés*-**Complexities for Generalized Models of Self-Assembly** - ↑
*Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine*-**Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues**- Natural Computing 7(3):347-370,2008
- Bibtex
**Author :**Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine**Title :**Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues**In :**Natural Computing -**Address :****Date :**2008

- ↑
*Erik Winfree*-**Self-healing Tile Sets**- Nanotechnology: Science and Computation pp. 55--78,2006
- http://dx.doi.org/10.1007/3-540-30296-4_4

Bibtex**Author :**Erik Winfree**Title :**Self-healing Tile Sets**In :**Nanotechnology: Science and Computation -**Address :****Date :**2006

- ↑
*Ho-Lin Chen, Ashish Goel, Chris Luhrs*-**Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly**- Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms pp. 409--418, Philadelphia, PA, USA,2008
- Bibtex
**Author :**Ho-Lin Chen, Ashish Goel, Chris Luhrs**Title :**Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly**In :**Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms -**Address :**Philadelphia, PA, USA**Date :**2008

- ↑
*Demaine, ErikD., Eisenstat, Sarah, Ishaque, Mashhood, Winslow, Andrew*-**One-dimensional staged self-assembly** - ↑
*Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, Hal Wasserman*-**Linear Self-Assemblies: Equilibria, Entropy and Convergence Rates**- In Sixth International Conference on Difference Equations and Applications ,2001
- Bibtex
**Author :**Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, Hal Wasserman**Title :**Linear Self-Assemblies: Equilibria, Entropy and Convergence Rates**In :**In Sixth International Conference on Difference Equations and Applications -**Address :****Date :**2001

- ↑
*Leonard Adleman*-**Toward a Mathematical Theory of Self-Assembly (Extended Abstract)**- Technical Report, University of Southern California (00-722),2000
- http://citeseer.ist.psu.edu/272447.html;
ftp://ftp.usc.edu/pub/csinfo/tech-reports/papers/00-722.ps.Z

Bibtex**Author :**Leonard Adleman**Title :**Toward a Mathematical Theory of Self-Assembly (Extended Abstract)**In :**Technical Report, University of Southern California -**Address :****Date :**2000

- ↑
*James I. Lathrop, Jack H. Lutz, Scott M. Summers*-**Strict Self-Assembly of Discrete Sierpinski Triangles**- Theoretical Computer Science 410:384--405,2009
- Bibtex
**Author :**James I. Lathrop, Jack H. Lutz, Scott M. Summers**Title :**Strict Self-Assembly of Discrete Sierpinski Triangles**In :**Theoretical Computer Science -**Address :****Date :**2009

- ↑
*Paul W. K. Rothemund*-**Theory and Experiments in Algorithmic Self-Assembly**- Ph.D. Thesis, University of Southern California , December 2001
- Bibtex
**Author :**Paul W. K. Rothemund**Title :**Theory and Experiments in Algorithmic Self-Assembly**In :**Ph.D. Thesis, University of Southern California -**Address :****Date :**December 2001