Producibility in hierarchical self-assembly
Pasadena
CA
USA
Three results are shown on producibility in the hierarchical model of tile self-assembly. It is shown that a simple greedy polynomial-time strategy decides whether an assembly $\alpha$ is producible. The algorithm can be optimized to use $O(|\alpha| \log^2 |\alpha|)$ time. Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow~\cite{TwoHandsBetterThanOne} showed that the problem of deciding if an assembly $\alpha$ is the unique producible terminal assembly of a tile system $\calT$ can be solved in $O(|\alpha|^2 |\calT| + |\alpha| |\calT|^2)$ time for the special case of noncooperative ``temperature 1'' systems. It is shown that this can be improved to $O(|\alpha| |\calT| \log |\calT|)$ time. Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently -- i.e., if the positions that they share have the same tile type in each assembly -- then their union is also producible.
abstract.tex
\begin{abstract}
  Three results are shown on producibility in the hierarchical model of tile self-assembly.

  It is shown that a simple greedy polynomial-time strategy decides whether an assembly $\alpha$ is producible.
  The algorithm can be optimized to use $O(|\alpha| \log^2 |\alpha|)$ time.

  Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow~\cite{TwoHandsBetterThanOne} showed that the problem of deciding if an assembly $\alpha$ is the unique producible terminal assembly of a tile system $\calT$ can be solved in $O(|\alpha|^2 |\calT| + |\alpha| |\calT|^2)$ time for the special case of noncooperative ``temperature 1'' systems.
  It is shown that this can be improved to $O(|\alpha| |\calT| \log |\calT|)$ time.

  Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently -- i.e., if the positions that they share have the same tile type in each assembly -- then their union is also producible.
\end{abstract}

% text abstract
% Title: Producibility in hierarchical self-assembly
%Three results are shown on producibility in the hierarchical model of tile self-assembly. It is shown that a simple greedy polynomial-time strategy decides whether an assembly A is producible. The algorithm can be optimized to use O(|A| log^2 |A|) time. Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow showed that the problem of deciding if an assembly A is the unique producible terminal assembly of a tile system T can be solved in O(|A|^2 |T| + |A| |T|^2) time for the special case of noncooperative "temperature 1" systems. It is shown that this can be improved to O(|A| |T| log |T|) time. Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently -- i.e., if the positions that they share have the same tile type in each assembly -- then their union is also producible.

% keywords
% hierarchical, self-assembly

alg-fast.tex
﻿
\begin{algorithm}
\caption{\textsc{Is-Producible-Assembly-Fast}$(\alpha,\tau)$}
\label{alg-fast}
\begin{algorithmic}[1]
  \STATE {\bf input:} assembly $\alpha$ and temperature $\tau$
  \STATE $V_c \leftarrow \setr{ \{v\} }{ v \in \dom \alpha }$\ \ \ // \emph{(positions defining) subassemblies of $\alpha$; initially individual (positions of) tiles}
  %\COMMENT{(positions defining) subassemblies of $\alpha$; initially individual (positions of) tiles}
  \STATE $E_c \leftarrow \{\{\{u\},\{v\}\} \ |\ \text{$\{u\} \in V_c$ and $\{v\} \in V_c$ and $u$ and $v$ are adjacent and interact} \}$
  \STATE $H \leftarrow $ empty heap
  \FORALL{$\{\{u\},\{v\}\} \in E_c$} \label{outer-for}
    \STATE $w(\{u\},\{v\}) \leftarrow $ strength of glue binding $\alpha(u)$ and $\alpha(v)$
    \STATE insert($\{\{u\},\{v\}\}, H)$
  \ENDFOR
  \WHILE{$|V_c| > 1$} \label{outer-while}
    \STATE $\{C_1,C_2\} \leftarrow $ remove-max($H$)\ \ \ // \emph{assume $|C_1| \geq |C_2|$ without loss of generality}
    %\COMMENT{assume $|C_1| \geq |C_2|$ W.L.O.G.}
    \label{repeat-body}
    \IF{$w(C_1,C_2) < \tau$}
      \PRINT{``$\alpha$ is not producible''}  and {\bf exit}
      %\STATE {\bf exit}
    \ENDIF
    \STATE remove $C_2$ from $V_c$
    \FORALL{neighbors $C$ of $C_2$} \label{inner-for}
      \STATE remove $\{C_2,C\}$ from $E_c$ and $H$ \label{remove}
      \IF{$\{C_1,C\} \in E_c$} \label{check-edge}
        \STATE $w(C_1,C) \leftarrow w(C_1,C) + w(C_2,C)$
        \STATE increase-key($\{C_1,C\},H)$\ \ \ // \emph{update edge $\{C_1,C\}$ with new weight}
        %\COMMENT{update edge $\{C_1,C\}$ with new weight}
        \label{increase-key}
      \ELSE
        \STATE $w(C_1,C) \leftarrow w(C_2,C)$
        \STATE add $\{C_1,C\}$ to $E_c$ and $H$
      \ENDIF
    \ENDFOR
  \ENDWHILE
  \PRINT{``$\alpha$ is producible''}
\end{algorithmic}
\end{algorithm}

alg-slow.tex
﻿
\begin{algorithm}
\caption{\textsc{Is-Producible-Assembly}$(\alpha,\tau)$}
\label{alg-slow}
\begin{algorithmic}[1]
  \STATE {\bf input:} assembly $\alpha$ and temperature $\tau$
  \STATE $\calC \leftarrow \setr{ \{v\} }{ v \in \dom \alpha }$\ \ \ // \emph{(positions defining) subassemblies of $\alpha$; initially individual (positions of) tiles}
  %\COMMENT{(positions of) subassemblies of $\alpha$; initially individual (positions of) tiles}
  \WHILE{$|\calC| > 1$} \label{start-while}
    \IF{there exist $C_i,C_j\in\calC$ with glues between $C_i$ and $C_j$ of total strength at least $\tau$} \label{get-glues}
      \STATE $\calC \leftarrow (\calC \setminus \{C_i,C_j\}) \cup \{ C_i \cup C_j \}$ \label{modify-C}
    \ELSE
      \PRINT{``$\alpha$ is not producible''} and {\bf exit}
%      \STATE {\bf exit}
    \ENDIF
  \ENDWHILE
  \PRINT{``$\alpha$ is producible''}
\end{algorithmic}
\end{algorithm}

algorithm.tex
﻿\section{Polynomial-time verification of production}
\label{sec-algorithm}

Let $S$ be a finite set.
A \emph{partition} of $S$ is a collection $\calC = \{ C_1, \ldots, C_k \} \subseteq \calP(S)$ such that $\bigcup_{i=1}^k C_i = S$ and for all $i \neq j$, $C_i \cap C_j = \emptyset$.
A \emph{hierarchical division} of $S$ is a full binary tree $\U$ (a tree in which every internal node has exactly two children) whose nodes represent subsets of $S$, such that the root of $\U$ represents $S$, the $|S|$ leaves of $\U$ represent the singleton sets $\{x\}$ for each $x \in S$, and each internal node has the property that its set is the (disjoint) union of its two childrens' sets.


\begin{lemma}\label{lem-partition-tree-partition}
Let $S$ be a finite set with $|S| \geq 2$.
Let $\U$ be any hierarchical division of $S$, and let $\calC$ be any partition of $S$ other than $\{S\}$.
Then there exist $C_1,C_2 \in \calC$ with $C_1 \neq C_2$, and there exist $C'_1 \subseteq C_1$ and $C'_2 \subseteq C_2$, such that $C'_1$ and $C'_2$ are siblings in $\U$.
\end{lemma}

\begin{proof}
First, label each leaf $\{x\}$ of $\U$ with the unique element $C_i \in \calC$ such that $x \in C_i$.
Next, iteratively label internal nodes according to the following rule: while there exist two children of a node $u$ that have the same label, assign that label to $u$.
Notice that this rule preserves the invariant that each labeled node $u$ (representing a subset of $S$) is a subset of the set its label represents.
Continue until no node has two identically-labeled children.
$\calC$ contains only proper subsets of $S$, so the root (which is the set $S$) cannot be contained in any of them, implying the root will remain unlabeled.
Follow any path starting at the root, always following an unlabeled child, until both children of the current internal node are labeled.
(The path may vacuously end at the root.)
Such a node is well-defined since at least all leaves are labeled.
By the stopping condition stated previously, these children must be labeled differently.
The children are the witnesses $C'_1$ and $C'_2$, with their labels having the values $C_1$ and $C_2$, testifying to the truth of the lemma.
\end{proof}

Lemma \ref{lem-partition-tree-partition} will be useful when we view $\Upsilon$ as an assembly tree for some producible assembly $\alpha$, and we view $\calC$ as a partially completed attempt to construct another assembly tree for $\alpha$, where each element of $\calC$ is a subassembly that has been produced so far.


When we say ``by monotonicity'', this refers to the fact that glue strengths are nonnegative, which implies that if two assemblies $\alpha$ and $\beta$ can attach, the addition of more tiles to either $\alpha$ or $\beta$ cannot \emph{prevent} this binding, so long as the additional tiles do not overlap the other assembly.

\input{alg-slow}
We want to solve the following problem: given an assembly $\alpha$ and temperature $\tau$, is $\alpha$ producible in the hierarchical aTAM at temperature $\tau$?\footnote{We do not need to give the tile set $T$ as input because the tiles in $\alpha$ implicitly define a tile set, and the presence of extra tile types in $T$ that do not appear in $\alpha$ cannot affect its producibility.}
The algorithm \textsc{Is-Producible-Assembly} (Algorithm~\ref{alg-slow}) solves this problem.

\begin{theorem}
  There is an $O(|\alpha| \log^2 |\alpha|)$ algorithm deciding whether an assembly $\alpha$ is producible at temperature $\tau$ in the hierarchical aTAM.
\end{theorem}

\begin{proof}
%\textsc{Is-Producible-Assembly} (Algorithm~\ref{alg-slow}) clearly runs in polynomial time.
%Appendix~\ref{sec-appendix-fast-alg} shows an optimized implementation that takes $O(n \log^2 n)$ time.
%It remains to justify that it is correct.
\noindent {\bf Correctness:}
\textsc{Is-Producible-Assembly} works by building up the initially edge-free graph with the tiles of $\alpha$ as its nodes (the algorithm stores the nodes as points in $\Z^2$, but $\alpha$ would be used in step \ref{get-glues} to get the glues and strengths between tiles at adjacent positions), stopping when the graph becomes connected.
The order in which connected components (implicitly representing assemblies) are removed from and added to $\calC$ implicitly defines a particular assembly tree with $\alpha$ at the root (for every $C_1,C_2$ processed in line \ref{modify-C}, the assembly $\alpha \upharpoonright (C_1 \cup C_2)$ is a parent of $\alpha \upharpoonright C_1$ and $\alpha \upharpoonright C_2$ in the assembly tree).
Therefore, if the algorithm reports that $\alpha$ is producible, then it is.
Conversely, suppose that $\alpha$ is producible via assembly tree $\Upsilon$. % be an assembly tree testifying that $\alpha$ is producible.
Let $\calC = \{C_1,\ldots,C_k\}$ be the set of assemblies at some iteration of the loop at line \ref{start-while}.
It suffices to show that some pair of assemblies $C_i$ and $C_j$ are connected by glues with strength at least $\tau$.
By Lemma \ref{lem-partition-tree-partition}, there exist $C_i$ and $C_j$ with subsets $C'_i \subseteq C_i$ and $C'_j \subseteq C_j$ such that $C'_i$ and $C'_j$ are sibling nodes in $\Upsilon$.
Because they are siblings, the glues between $C'_i$ and $C'_j$ have strength at least $\tau$.
By monotonicity these glues suffice to bind $C_i$ to $C_j$,
so \textsc{Is-Producible-Assembly} is correct.

\noindent{\bf Running time:} \input{appendix-fast-alg}
\end{proof}

appendix-fast-alg.tex
﻿Let $n=|\alpha|$.
The running time of the \textsc{Is-Producible-Assembly} (Algorithm~\ref{alg-slow}) is polynomial in $n$, but the algorithm can be optimized to improve the running time to $O(n \log^2 n)$ by careful choice of data structures.
\textsc{Is-Producible-Assembly-Fast} (Algorithm~\ref{alg-fast}) shows pseudo-code for this optimized implementation, which we now describe.
Let $n = |\alpha|$. %\footnote{Technically the input size in bits is $\Theta(n \log n)$, but we pretend it is $n$ (which makes the running time appear a log factor slower) and also pretend that comparisons, etc., take constant time instead of log time (which makes the running time appear a log factor faster), so the derived running time will be accurate.}
Instead of searching over all pairs of assemblies, only search those pairs of assemblies that are adjacent.
This number is $O(n)$ since a grid graph has degree at most 4 (hence $O(n)$ edges) and the number of edges in the full grid graph of $\alpha$ is an upper bound on the number of adjacent assemblies at any time.
This can be encoded in a dynamically changing graph $G_c$ whose nodes are the current set of assemblies and whose edges connect those assemblies that are adjacent.

\input{alg-fast}
Each edge of $G_c$ stores the total glue strength between the assemblies.
Whenever two assemblies $C_1$ and $C_2$, with $|C_1| \geq |C_2|$ without loss of generality, are combined to form a new assembly, $G_c$ is updated by removing $C_2$, merging its edges with those of $C_1$, and for any edges they already share (i.e., the neighbor on the other end of the edge is the same), summing the strengths on the edges.
Each update of an edge (adding it to $C_1$, or finding it in $C_1$ to update its strength) can be done in $O(\log n)$ time using a tree set data structure to store neighbors for each assembly.

We claim that the total number of such updates of all edges is $O(n \log n)$ over all time, or amortized $O(\log n)$ updates per iteration of the outer loop.
To see why, observe that the number of edges an assembly has is at most linear in its size, so the number of new edges that must be added to $C_1$, or existing edges in $C_1$ whose strengths must be updated, is at most (within a constant) the size of the smaller component $C_2$.
The total number of edge updates is then, if $\Upsilon$ is the assembly tree discovered by the algorithm, $\sum_{\text{nodes } u \in \Upsilon} \min\{|\text{left}(u)|,|\text{right}(u)|\}$, where $|\text{left}(u)|$ and $|\text{right}(u)|$ respectively refer to the number of leaves of $u$'s left and right subtrees.
For a given number $n$ of leaves, this sum is maximized with a balanced tree, and in that case (summing over all levels of the tree) is $\sum_{i=0}^{\log n} 2^i (n / 2^i) = O(n \log n)$.
So the total time to update all edges is $O(n \log^2 n)$.

As for actually finding $C_1$ and $C_2$, each iteration of the outer loop, we can just look for the pair of adjacent assemblies with the largest connection strength.
So store the edges in a heap and we can simply grab the strongest edge off the top and update the heap by updating the keys containing $C_1$ whose connection strength changed and removing those containing $C_2$ but not $C_1$.
The edges whose connection strength changed correspond to precisely those neighbors that $C_1$ and $C_2$ shared before being merged.
Therefore $|C_2|$ is an upper bound on the number of edge updates required.
Thus the amortized number of heap updates is $O(\log n)$ per iteration of the outer loop by the same argument as above.
Thus it takes amortized time $O(\log^2 n)$ per iteration if each heap operation is $O(\log n)$.
Therefore (this non-naive implementation of) the algorithm takes $O(n \log^2 n)$ time.

The algorithm \textsc{Is-Producible-Assembly-Fast} (Algorithm~\ref{alg-fast}) implements this optimized idea.
The terminology for heap operations is taken from~\cite{CLRS01}.
Note that the way we remove $C_1$ and $C_2$ and add their union is to simply delete $C_2$ and then update $C_1$ to contain $C_2$'s edges.
The graph $G_c$ discussed above is $G_c = (V_c,E_c)$ where $V_c$ and $E_c$ are variables in \textsc{Is-Producible-Assembly-Fast}.
The weight function $w$ is used by the heap $H$ to order its elements.



Summarizing the analysis, each data structure operation takes time $O(\log n)$ with appropriate choice of a backing data structure.
The two outer loops (lines~\ref{outer-for} and~\ref{outer-while}) take $O(n)$ iterations.
The inner loop (line~\ref{inner-for}) runs for amortized $O(\log n)$ iterations, and its body executes a constant number of $O(\log n)$ time operations.
Therefore the total running time is $O(n \log^2 n)$.

conclusion.tex
\section{Conclusion}
\label{sec-conclusion}

Theorem~\ref{thm-union-producible} shows that if assemblies $\alpha$ and $\beta$ overlap consistently, then $\alpha \cup \beta$ is producible.
What if $\alpha=\beta$?
Suppose we have three copies of $\alpha$, and label them each uniquely as $\alpha_1,\alpha_2,\alpha_3$.
Suppose further than $\alpha_2$ overlaps consistently with $\alpha_1$ when translated by some non-zero vector $\vv$.
Then we know that $\alpha_1 \cup \alpha_2$ is producible.
Suppose that $\alpha_3$ is $\alpha_2$ translated by $\vv$, or equivalently it is $\alpha_1$ translated by $2 \vv$.
Then $\alpha_2 \cup \alpha_3$ is producible, since this is merely a translated copy of $\alpha_1 \cup \alpha_2$.
It seems intuitively that $\alpha_1 \cup \alpha_2 \cup \alpha_3$ should be producible as well.
However, while $\alpha_1$ overlaps consistently with $\alpha_2$, and $\alpha_2$ overlaps consistently with $\alpha_3$, it could be the case that $\alpha_3$ intersects $\alpha_1$ inconsistently, i.e., they share a position but put a different tile type at that position.
In this case $\alpha_1 \cup \alpha_2 \cup \alpha_3$ is undefined.
See Figure~\ref{fig:pump} for an example.

\begin{figure}[htb]
\begin{center}
  \includegraphics[width=6in]{figures/pump}
  \caption{\label{fig:pump} \figuresize
  (a) A producible assembly $\alpha$. Gray tiles are all distinct types from each other, but red, green, and blue each represent one of three different tile types, so the two blue tiles are the same type.
  (b) By Theorem~\ref{thm-union-producible}, $\alpha_1 \cup \alpha_2$ is producible, where $\alpha_1 = \alpha$ and $\alpha_2 = \alpha_1 + (2,-2)$, because they overlap in only one position, and they both have the blue tile type there.
  (c) $\alpha_1$ and $\alpha_3$ both have a tile at the same position, but the types are different (red in the case of $\alpha_1$ and green in the case of $\alpha_3$).
  (d) However, a subassembly $\alpha'_i$ of each new $\alpha_i$ can grow, enough to allow the translated equivalent subassembly $\alpha'_{i+1}$ of $\alpha_{i+1}$ to grow from $\alpha'_i$, so an infinite structure is producible.
  }
\end{center}
\end{figure}

However, in this case, although $\alpha_1 \cup \alpha_2 \cup \alpha_3$ is not producible (in fact, not even defined), ``enough'' of $\alpha_3$ (say, $\alpha'_3 \sqsubset \alpha_3$) can grow off of $\alpha_1 \cup \alpha_2$ to allow a fourth copy $\alpha'_4$ to begin to grow to an assembly to which a fifth copy $\alpha'_5$ can attach, etc., so that an infinite assembly can grow by ``pumping'' additional copies of $\alpha'_3$.
Is this always possible?
In other words, is it the case that if $\alpha$ is a producible assembly of a hierarchical TAS $\calT$, and $\alpha$ overlaps consistently with some non-zero translation of itself, then $\calT$ necessarily produces an infinite assembly?
If true, this would imply that no hierarchical TAS producing such an assembly could be uniquely produce a finite shape.
This would settle an open question posed by Chen and Doty~\cite{CheDot12}, who showed that as long as a hierarchical TAS does not produce assemblies that consistently overlap any translation of themselves, then the TAS cannot uniquely produce any shape in time sublinear in its diameter.

intro-dolemite.tex
﻿\vspace{-1.1cm}
\section{Introduction}
\label{sec-intro}

\subsection{Background of the field}
Winfree's abstract Tile Assembly Model (aTAM)~\cite{Winfree98simulationsof} is a model of crystal growth through cooperative binding of square-like monomers called \emph{tiles}, implemented experimentally (for the current time) by DNA~\cite{WinLiuWenSee98, BarSchRotWin09}.
In particular, it models the potentially algorithmic capabilities of tiles that can be designed to bind if and only if the total strength of attachment (summed over all binding sites, called \emph{glues} on the tile) is at least a parameter $\tau$, sometimes called the \emph{temperature}.
In particular, when the glue strengths are integers and $\tau=2$, this implies that two strength 1 glues must cooperate to bind the tile to a growing assembly.
Two assumptions are key: 1) growth starts from a single specially designated \emph{seed} tile type, and 2) only individual tiles bind to an assembly, never larger assemblies consisting of more than one tile type.
We will refer to this model as the \emph{seeded aTAM}.
While violations of these properties are often viewed as errors in implementation of the seeded aTAM~\cite{SchWin07, SchWin09}, relaxing the assumptions results in a different model with its own programmable abilities.
In the \emph{hierarchical} (a.k.a. \emph{multiple tile}~\cite{AGKS05}, \emph{polyomino}~\cite{Winfree06, Luhrs10}, \emph{two-handed}~\cite{TwoHandsBetterThanOne, DotPatReiSchSum10, TwoHandedNotIntrinsicallyUniversalconf}) \emph{aTAM}, there is no seed tile, and an assembly is considered producible so long as two producible assemblies are able to attach to each other with strength at least $\tau$, with all individual tiles being considered as ``base case'' producible assemblies.
In either model, an assembly is considered \emph{terminal} if nothing can attach to it; viewing self-assembly as a computation, terminal assembly(ies) are often interpreted to be the output.
See~\cite{DotCACM} for an introduction to recent work in these models.

The hierarchical aTAM has attracted considerable recent attention.
%
It is $\coNP$-complete to decide whether an assembly is the unique terminal assembly produced by a hierarchical tile system~\cite{TwoHandsBetterThanOne}.
%
There are infinite shapes that can be assembled in the hierarchical aTAM but not the seeded aTAM, and vice versa, and there are finite shapes requiring strictly more tile types to assemble in the seeded aTAM than the hierarchical aTAM, and vice versa~\cite{TwoHandsBetterThanOne}.
%
Despite this incomparability between the models for exact assembly of shapes, with a small blowup in scale, any seeded tile system can be simulated by a hierarchical tile system~\cite{TwoHandsBetterThanOne}, improving upon an earlier scheme that worked for restricted classes of seeded tile systems~\cite{Luhrs10}.
%
However, the hierarchical aTAM is not able to simulate itself from a single set of tile types, i.e., it is not \emph{intrinsically universal}~\cite{TwoHandedNotIntrinsicallyUniversalconf}, unlike the seeded aTAM~\cite{TAMIU}.
%
It is possible to assemble an $n \times n$ square in a hierarchical tile system with $O(\log n)$ tile types that exhibits a very strong form of fault-tolerance in the face of spurious growth via strength 1 bonds~\cite{DotPatReiSchSum10}.
%
The parallelism of the hierarchical aTAM suggests the possibility that it can assemble shapes faster than the seeded aTAM, but it cannot for a wide class of tile systems~\cite{CheDot12}.

Interesting variants of the hierarchical aTAM introduce other assumptions to the model.
The \emph{multiple tile} model retains a seed tile and places a bound on the size of assemblies attaching to it~\cite{AGKS05}.
%
Under this model, it is possible to modify a seeded tile system to be \emph{self-healing}, that is, it correctly regrows when parts of itself are removed, even if the attaching assemblies that refill the removed gaps are grown without the seed~\cite{Winfree06}.
%
The model of \emph{staged assembly} allows multiple test tubes to undergo independent growth, with excess incomplete assemblies washed away (e.g. purified based on size) and then mixed, with assemblies from each tube combining via hierarchical attachment~\cite{DDFIRSS07, DemEisIshWinOneDimStagedjournal}.
%
The \emph{RNase enzyme} model~\cite{RNaseSODA2010, DemPatSchSum2010RNase, PatSumIdentifyingJournal} assumes some tile types to be made of RNA, which can be digested by an enzyme called RNase, leaving only the DNA tiles remaining, and possibly disconnecting what was previously a single RNA/DNA assembly into multiple DNA assemblies that can combine via hierarchical attachment.
%
Introducing negative glue strengths into the hierarchical aTAM allows for ``fuel-efficient'' computation~\cite{SchSheSODAFuel}.




\subsection{Contributions of this paper}
We show three results related to producibility in the hierarchical aTAM.
\begin{enumerate}
  \item
  In the seeded aTAM, there is an obvious linear-time algorithm to test whether assembly $\alpha$ is producible by a tile system: starting from the seed, try to attach tiles until $\alpha$ is complete or no more attachments are possible.
  We show that in the hierarchical aTAM, a similar greedy strategy correctly identifies whether a given assembly is producible, though it is more involved to prove that it is correct.
  The idea is to start with all tiles in place as they appear in $\alpha$, but with no bonds, and then to greedily bind attachable assemblies until $\alpha$ is assembled.
  The algorithm can be optimized to use $O(n \log^2 n)$ time.
  It is not obvious that this works, since it is conceivable that assemblies must attach in a certain order for $\alpha$ to form, but the greedy strategy may pick another order and hit a dead-end in which no assemblies can attach.
  This is shown in Section~\ref{sec-algorithm}.

  \item
  We show that there is a faster algorithm for the temperature 1 Unique Production Verification (UPV) problem studied by Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow~\cite{TwoHandsBetterThanOne}, which is the problem of determining whether assembly $\alpha$ is the unique producible terminal assembly of tile system $\calT$, where $\calT$ has temperature 1, meaning that all positive glue strength are sufficiently strong to attach any two assemblies.
  They give an algorithm that runs in $O(n^2)$ time.
  We show how to improve this running time.
  Cannon et al.~proved their result by using an $O(n^2)$ time algorithm for UPV that works in the seeded aTAM~\cite{ACGHKMR02}, and then reduced the hierarchical temperature-1 UPV problem to instances of the seeded UPV problem.
  We improve this result by showing that a faster $O(n \log n)$ time algorithm for the seeded UPV problem exists for the special case of temperature 1, implying that the algorithm of Cannon et al.~for the hierarchical model can thus be made to run in $O(n \log n)$ time.
  This is shown in Section~\ref{sec-upv-t1}.
  %We also show a direct (and simpler) $O(n)$ time algorithm for the hierarchical temperature-1 UPV problem.
  %We include the former algorithm because the seeded result may be of independent interest.
  %In particular, the connection between mismatches and biconnected components of the binding graph may have implications for an open question~\cite{DotPatSum11} regarding the computational power of the seeded temperature 1 aTAM.

  \item
  We show that if two assemblies $\alpha$ and $\beta$ are producible in the hierarchical model, and if they can be overlapped consistently (i.e., if the positions that they share have the same tile type in each assembly), then their union $\alpha \cup \beta$ is producible.
  This is trivially true in the seeded model, but it requires much more care to prove in the hierarchical model.
  It is conceivable \emph{a priori} that although $\beta$ is producible, $\beta$ must assemble $\alpha \cap \beta$ in some order that is inconsistent with how $\alpha$ assembles $\alpha \cap \beta$.
  This is shown in Section~\ref{sec-union}.
\end{enumerate}


intro.tex
﻿\vspace{-1.1cm}
\section{Introduction}
\label{sec-intro}

\subsection{Background of the field}
Winfree's abstract Tile Assembly Model (aTAM)~\cite{Winfree98simulationsof} is a model of crystal growth through cooperative binding of square-like monomers called \emph{tiles}, implemented experimentally (for the current time) by DNA~\cite{WinLiuWenSee98, BarSchRotWin09}.
In particular, it models the potentially algorithmic capabilities of tiles that can be designed to bind if and only if the total strength of attachment (summed over all binding sites, called \emph{glues} on the tile) is at least a parameter $\tau$, sometimes called the \emph{temperature}.
In particular, when the glue strengths are integers and $\tau=2$, this implies that two strength 1 glues must cooperate to bind the tile to a growing assembly.
Two assumptions are key: 1) growth starts from a single specially designated \emph{seed} tile type, and 2) only individual tiles bind to an assembly, never larger assemblies consisting of more than one tile type.
We will refer to this model as the \emph{seeded aTAM}.
While violations of these properties are often viewed as errors in implementation of the seeded aTAM~\cite{SchWin07, SchWin09}, relaxing the assumptions results in a different model with its own programmable abilities.
In the \emph{hierarchical} (a.k.a. \emph{multiple tile}~\cite{AGKS05}, \emph{polyomino}~\cite{Winfree06, Luhrs10}, \emph{two-handed}~\cite{TwoHandsBetterThanOne, DotPatReiSchSum10, TwoHandedNotIntrinsicallyUniversalconf}) \emph{aTAM}, there is no seed tile, and an assembly is considered producible so long as two producible assemblies are able to attach to each other with strength at least $\tau$, with all individual tiles being considered as ``base case'' producible assemblies.
In either model, an assembly is considered \emph{terminal} if nothing can attach to it; viewing self-assembly as a computation, terminal assembly(ies) are often interpreted to be the output.
See~\cite{DotCACM,PatitzSurvey12} for an introduction to recent work in these models.

The hierarchical aTAM has attracted considerable recent attention.
%
It is $\coNP$-complete to decide whether an assembly is the unique terminal assembly produced by a hierarchical tile system~\cite{TwoHandsBetterThanOne}.
%
There are infinite shapes that can be assembled in the hierarchical aTAM but not the seeded aTAM, and vice versa, and there are finite shapes requiring strictly more tile types to assemble in the seeded aTAM than the hierarchical aTAM, and vice versa~\cite{TwoHandsBetterThanOne}.
%
Despite this incomparability between the models for exact assembly of shapes, with a small blowup in scale, any seeded tile system can be simulated by a hierarchical tile system~\cite{TwoHandsBetterThanOne}, improving upon an earlier scheme that worked for restricted classes of seeded tile systems~\cite{Luhrs10}.
%
However, the hierarchical aTAM is not able to simulate itself from a single set of tile types, i.e., it is not \emph{intrinsically universal}~\cite{TwoHandedNotIntrinsicallyUniversalconf}, unlike the seeded aTAM~\cite{TAMIU}.
%
It is possible to assemble an $n \times n$ square in a hierarchical tile system with $O(\log n)$ tile types that exhibits a very strong form of fault-tolerance in the face of spurious growth via strength 1 bonds~\cite{DotPatReiSchSum10}.
%
The parallelism of the hierarchical aTAM suggests the possibility that it can assemble shapes faster than the seeded aTAM, but it cannot for a wide class of tile systems~\cite{CheDot12}.

Interesting variants of the hierarchical aTAM introduce other assumptions to the model.
The \emph{multiple tile} model retains a seed tile and places a bound on the size of assemblies attaching to it~\cite{AGKS05}.
%
Under this model, it is possible to modify a seeded tile system to be \emph{self-healing}, that is, it correctly regrows when parts of itself are removed, even if the attaching assemblies that refill the removed gaps are grown without the seed~\cite{Winfree06}.
%
The model of \emph{staged assembly} allows multiple test tubes to undergo independent growth, with excess incomplete assemblies washed away (e.g. purified based on size) and then mixed, with assemblies from each tube combining via hierarchical attachment~\cite{DDFIRSS07, DemEisIshWinOneDimStagedjournal}.
%
The \emph{RNase enzyme} model~\cite{RNaseSODA2010, DemPatSchSum2010RNase, PatSumIdentifyingJournal} assumes some tile types to be made of RNA, which can be digested by an enzyme called RNase, leaving only the DNA tiles remaining, and possibly disconnecting what was previously a single RNA/DNA assembly into multiple DNA assemblies that can combine via hierarchical attachment.
%
Introducing negative glue strengths into the hierarchical aTAM allows for ``fuel-efficient'' computation~\cite{SchSheSODAFuel}.




\subsection{Contributions of this paper}
We show three results related to producibility in the hierarchical aTAM.
\begin{enumerate}
  \item
  In the seeded aTAM, there is an obvious linear-time algorithm to test whether assembly $\alpha$ is producible by a tile system: starting from the seed, try to attach tiles until $\alpha$ is complete or no more attachments are possible.
  We show that in the hierarchical aTAM, a similar greedy strategy correctly identifies whether a given assembly is producible, though it is more involved to prove that it is correct.
  The idea is to start with all tiles in place as they appear in $\alpha$, but with no bonds, and then to greedily bind attachable assemblies until $\alpha$ is assembled.
  The algorithm can be optimized to use $O(|\alpha| \log^2 |\alpha|)$ time.
  It is not obvious that this works, since it is conceivable that assemblies must attach in a certain order for $\alpha$ to form, but the greedy strategy may pick another order and hit a dead-end in which no assemblies can attach.
  This is shown in Section~\ref{sec-algorithm}.

  \item
  We show that there is a faster algorithm for the temperature 1 Unique Production Verification (UPV) problem studied by Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow~\cite{TwoHandsBetterThanOne}, which is the problem of determining whether assembly $\alpha$ is the unique producible terminal assembly of tile system $\calT$, where $\calT$ has temperature 1, meaning that all positive glue strength are sufficiently strong to attach any two assemblies.
  They give an algorithm that runs in $O(|\alpha|^2 |\calT| + |\alpha| |\calT|^2)$ time.
  We show how to improve this running time.
  Cannon et al.~proved their result by using an $O(|\alpha|^2 + |\alpha| |\calT|)$ time algorithm for UPV that works in the seeded aTAM~\cite{ACGHKMR02}, and then reduced the hierarchical temperature-1 UPV problem to $|\calT|$ instances of the seeded UPV problem.
  We improve this result by showing that a faster $O(|\alpha| \log |\calT|)$ time algorithm for the seeded UPV problem exists for the special case of temperature 1, and then we apply the technique of Cannon et al.~relating the hierarchical problem to the seeded problem to improve the running time of the hierarchical algorithm to $O(|\alpha| |\calT| \log |\calT|)$.
  This is shown in Section~\ref{sec-upv-t1}.
  %We also show a direct (and simpler) $O(n)$ time algorithm for the hierarchical temperature-1 UPV problem.
  %We include the former algorithm because the seeded result may be of independent interest.
  %In particular, the connection between mismatches and biconnected components of the binding graph may have implications for an open question~\cite{DotPatSum11} regarding the computational power of the seeded temperature 1 aTAM.

  \item
  We show that if two assemblies $\alpha$ and $\beta$ are producible in the hierarchical model, and if they can be overlapped consistently (i.e., if the positions that they share have the same tile type in each assembly), then their union $\alpha \cup \beta$ is producible.
  This is trivially true in the seeded model, but it requires more care to prove in the hierarchical model.
  It is conceivable \emph{a priori} that although $\beta$ is producible, $\beta$ must assemble $\alpha \cap \beta$ in some order that is inconsistent with how $\alpha$ assembles $\alpha \cap \beta$.
  This is shown in Section~\ref{sec-union}.
\end{enumerate}


main.tex
\documentclass[11pt]{article} \usepackage[normal]{optional}
%\documentclass[11pt]{article} \usepackage[submission]{optional}
%\documentclass[oribibl,11pt,a4paper]{llncs}  \usepackage[final]{optional}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{graphicx}
\usepackage{ifpdf}
\usepackage{cite}
\usepackage{comment}
\usepackage{subfigure}
\usepackage{todonotes} \newcommand{\todoi}[1]{\todo[inline]{#1}}

\newcommand{\figuresize}{\small}

\opt{normal,submission}{\usepackage{commands-tam,numbering-tam}}


\usepackage{amsfonts}
\opt{normal,submission}{\usepackage{amsthm}}
\usepackage{fullpage}

\newcommand{\U}{\Upsilon}
\newcommand{\Ua}{\Upsilon_\alpha}
\newcommand{\Ub}{\Upsilon_\beta}


\newcommand{\dN}{\mathsf{N}}
\newcommand{\dS}{\mathsf{S}}
\newcommand{\dE}{\mathsf{E}}
\newcommand{\dW}{\mathsf{W}}
\newcommand{\dall}{\{\dN,\dS,\dE,\dW\}}
\newcommand{\oneTo}[1]{\{1,\ldots,#1\}}
\newcommand{\ha}{\widehat{\alpha}}
\newcommand{\ta}{\alpha}
\newcommand{\tb}{\beta}
\newcommand{\tg}{\gamma}
\renewcommand{\exp}[1]{\mathrm{E}\left[ #1 \right]}
\renewcommand{\time}{\mathbf{T}}
\newcommand{\timeS}{\mathsf{T}^\mathrm{s}}
\newcommand{\timeH}{\mathsf{T}^\mathrm{h}}
\newcommand{\Kddac}{\mathrm{depth}^\mathrm{da}}
\newcommand{\blank}{\llcorner\negthinspace\lrcorner}
\newcommand{\ignore}[1]{}
\newcommand{\w}[1]{\widetilde{#1}}
\newcommand{\wa}{\w{\alpha}}
\newcommand{\wb}{\w{\beta}}
\newcommand{\wg}{\w{\gamma}}
\newcommand{\bL}{\mathbf{L}}
\newcommand{\bT}{\mathbf{T}}
\newcommand{\vv}{\vec{v}}


\newcommand{\hUPV}{{\normalfont \textsf{hUPV}_1}}
\newcommand{\sUPV}{{\normalfont \textsf{sUPV}_1}}

\ifpdf
  % one of these two:
  %\usepackage[pdftex]{graphicx}  % note the x at the end
  \usepackage[pdftex]{epsfig}
  % hyperref should be the last package loaded:
  %\usepackage[pdftex]{hyperref}
  \usepackage{pageno}
  \usepackage[pdfstartview={XYZ null null 1.00},pdfpagemode=None,colorlinks=true,citecolor=blue,linkcolor=blue]{hyperref}
  %\hypersetup{pdfstartview={XYZ null null 1.00}}
\else
    % one of these two:
    %\usepackage[dvips]{graphicx}  % note the x at the end
    \usepackage[dvips]{epsfig}
    % make the command \href from hyperref available as a 'print only'
    %\newcommand{\href}[2]{#2}
    \usepackage[dvips,colorlinks=true,citecolor=blue,linkcolor=blue]{hyperref}
\fi

% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
% MATH -----------------------------------------------------------

% Alter some LaTeX defaults for better treatment of figures:
    % See p.105 of "TeX Unbound" for suggested values.
    % See pp. 199-200 of Lamport's "LaTeX" book for details.
    %   General parameters, for ALL pages:
    \renewcommand{\topfraction}{0.9}    % max fraction of floats at top
    \renewcommand{\bottomfraction}{0.8} % max fraction of floats at bottom
    %   Parameters for TEXT pages (not float pages):
    \setcounter{topnumber}{2}
    \setcounter{bottomnumber}{2}
    \setcounter{totalnumber}{4}     % 2 may work better
    \setcounter{dbltopnumber}{2}    % for 2-column pages
    \renewcommand{\dbltopfraction}{0.9} % fit big float above 2-col. text
    \renewcommand{\textfraction}{0.07}  % allow minimal text w. figs
    %   Parameters for FLOAT pages (not text pages):
    \renewcommand{\floatpagefraction}{0.7}  % require fuller float pages
    % N.B.: floatpagefraction MUST be less than topfraction !!
    \renewcommand{\dblfloatpagefraction}{0.7}   % require fuller float pages


% ----------------------------------------------------------------

\begin{document}

\title{Producibility in hierarchical self-assembly}

\author{
    David Doty\thanks{California Institute of Technology, Pasadena, CA, USA, {\tt ddoty@caltech.edu}. The author was supported by the Molecular Programming Project under NSF grant 0832824 and by NSF grants CCF-1219274 and CCF-1162589, and by a Computing Innovation Fellowship under NSF grant 1019343.}
}
\date{}

\maketitle
\input{abstract}\thispagestyle{empty}\newpage\setcounter{page}{1}
\input{intro}
\vspace{-0.2in}
\input{tam-informal}
\vspace{-0.2in}
\input{algorithm}
\vspace{-0.2in}
\input{upv-t1}
\vspace{-0.2in}
\input{union}
\vspace{-0.2in}
\input{conclusion}

\paragraph{Acknowledgements.}
The author is very grateful to Ho-Lin Chen, David Soloveichik, Damien Woods, Matt Patitz, Scott Summers, Robbie Schweller, J\'{a}n Ma{\v{n}}uch, and Ladislav Stacho for many insightful discussions.

\newpage
\bibliographystyle{plain}
\bibliography{tam}
\newpage



\newpage
\appendix
\section{Formal definition of the abstract tile assembly model}
\label{sec-tam-formal}
\input{tam-formal}

%\section{Optimized implementation of \textsc{Is-Producible-Assembly}}
%\label{sec-appendix-fast-alg}
%\input{appendix-fast-alg}


\end{document}
% ----------------------------------------------------------------

tam-formal.tex

\newcommand{\fullgridgraph}{G^\mathrm{f}}
\newcommand{\bindinggraph}{G^\mathrm{b}}

This section gives a terse definition of the abstract Tile Assembly Model (aTAM,~\cite{Winf98}). This is not a tutorial; for readers unfamiliar with the aTAM,  \cite{RotWin00} gives an excellent introduction to the model.

Fix an alphabet $\Sigma$. $\Sigma^*$ is the set of finite strings over $\Sigma$.
Given a discrete object $O$, $\langle O \rangle$ denotes a standard encoding of $O$ as an element of $\Sigma^*$.
$\Z$, $\Z^+$, and $\N$ denote the set of integers, positive integers, and nonnegative integers, respectively.
%For all $n \in \N$, $[n]$ denotes the set $\{0, 1, \ldots, n-1\}$.
For a set $A$, $\calP(A)$ denotes the power set of $A$.
Given $A \subseteq \Z^2$, the \emph{full grid graph} of $A$ is the undirected graph $\fullgridgraph_A=(V,E)$, where $V=A$, and for all $u,v\in V$, $\{u,v\} \in E \iff \| u-v\|_2 = 1$; i.e., if and only if $u$ and $v$ are adjacent on the integer Cartesian plane.
A \emph{shape} is a set $S \subseteq \Z^2$ such that $\fullgridgraph_S$ is connected.
%A shape $S$ is a \emph{tree} if $\fullgridgraph_S$ is acyclic.


A \emph{tile type} is a tuple $t \in (\Sigma^* \times \N)^4$; i.e., a unit square with four sides listed in some standardized order, each side having a \emph{glue label} (a.k.a. \emph{glue}) $\ell \in \Sigma^*$ and a nonnegative integer \emph{strength}, denoted $str(\ell)$.
For a set of tile types $T$, let $\Lambda(T) \subset \Sigma^*$ denote the set of all glue labels of tile types in $T$.
If a glue has strength 0, we say it is \emph{null}, and if a positive-strength glue facing some direction does not appear on some tile type in the opposite direction, we say it is \emph{functionally null}.
We assume that all tile sets in this paper contain no functionally null glues.\footnote{This assumption does not affect the results of this paper.
    It is irrelevant for Theorem~\ref{thm-union-producible} or the correctness of the algorithms in the other theorems.
    It also does not affect the running time results for algorithms taking a TAS as input, because we can preprocess $T$ in linear time to find and set to null any functionally null glues.
    The number of glues is $O(|T|)$, and we assume that each glue from glue set $G$ is an integer in the set $\{0,\ldots,|G|-1\}$.
    We can use a Boolean array of size $|G|$ to determine in time $O(|T|)$ which glues appear on the north that do not appear on the south of some tile type.
    Repeat this for each of the remaining three directions.
    Then replace all functionally null glues in $T$ with null glues, which takes time $O(|T|)$.
    To do this replacement in an assembly $\alpha$ takes time $O(|\alpha|)$.}
Let $\dall$ denote the \emph{directions} consisting of unit vectors $\{(0,1), (0,-1), (1,0), (-1,0)\}$.
Given a tile type $t$ and a direction $d \in \dall$, $t(d) \in \Lambda(T)$ denotes the glue label on $t$ in direction $d$.
We assume a finite set $T$ of tile types, but an infinite number of copies of each tile type, each copy referred to as a \emph{tile}. An \emph{assembly}
is a nonempty connected arrangement of tiles on the integer lattice $\Z^2$, i.e., a partial function $\alpha:\Z^2 \dashrightarrow T$ such that $\fullgridgraph_{\dom \alpha}$ is connected and $\dom \alpha \neq \emptyset$.
The \emph{shape of $\alpha$} is $\dom \alpha$.
Write $|\alpha|$ to denote $|\dom\alpha|$.
Given two assemblies $\alpha,\beta:\Z^2 \dashrightarrow T$, we say $\alpha$ is a \emph{subassembly} of $\beta$, and we write $\alpha \sqsubseteq \beta$, if $\dom \alpha \subseteq \dom \beta$ and, for all points $p \in \dom \alpha$, $\alpha(p) = \beta(p)$.

Given two assemblies $\alpha$ and $\beta$, we say $\alpha$ and $\beta$ are \emph{equivalent up to translation}, written $\alpha \simeq \beta$, if there is a vector $\vec{x} \in \Z^2$ such that $\dom\alpha = \dom\beta + \vec{x}$ (where for $A \subseteq \Z^2$, $A + \vec{x}$ is defined to be $\setr{p + \vec{x}}{p \in A}$) and for all $p \in \dom\beta$, $\alpha(p + \vec{x}) = \beta(p)$.
In this case we say that $\beta$ is a \emph{translation} of $\alpha$.
%Given a shape $S \subseteq \Z^2$, we say that $S$ is \emph{canonical} if $S \subseteq \N^2$, $(x,0) \in S$ for some $x\in\N$, and $(0,y) \in S$ for some $y\in\N$.
%In other words, $S$ is located entirely in the first quadrant, but at far to the left and down as possible.
%We say an assembly $\alpha$ is \emph{canonical} if $\dom\alpha$ is canonical.
%For each finite assembly $\alpha$, there is exactly one canonical assembly $\wa$ such that $\alpha \simeq \wa$.
%Given such a finite $\alpha$, we say $\wa$ is the \emph{canonical assembly of $\alpha$}.
%For brevity and clarity, we will tend to abuse notation and speak of assemblies equivalent up to translation as if they are the same object, often taking $\alpha$ to mean $\wa$, particularly when discussing concentrations.
We have fixed assemblies at certain positions on $\Z^2$ only for mathematical convenience in some contexts, but of course real assemblies float freely in solution and do not have a fixed position.

%A \emph{strength function} is a function $g:\Lambda(T)\to\N$ indicating, for each glue label $\ell$, the strength $str(\ell)$ with which it binds.
Let $\alpha$ be an assembly and let $p\in\dom\alpha$ and $d\in\dall$ such that $p + d \in \dom\alpha$.
Let $t=\alpha(p)$ and $t' = \alpha(p+d)$.
We say that the tiles $t$ and $t'$ at positions $p$ and $p+d$ \emph{interact} if $t(d) = t'(-d)$ and $str(t(d)) > 0$, i.e., if the glue labels on their abutting sides are equal and have positive strength.
Each assembly $\alpha$ induces a \emph{binding graph} $\bindinggraph_\alpha$, a grid graph $G=(V_\alpha,E_\alpha)$, where $V_\alpha=\dom\alpha$, and $\{p_1,p_2\} \in E_\alpha \iff \alpha(p_1) \text{ interacts with } \alpha(p_2)$.\footnote{For $\fullgridgraph_{\dom \alpha}=(V_{\dom \alpha},E_{\dom \alpha})$ and $\bindinggraph_\alpha=(V_\alpha,E_\alpha)$, $\bindinggraph_\alpha$ is a spanning subgraph of $\fullgridgraph_{\dom \alpha}$: $V_\alpha = V_{\dom \alpha}$ and $E_\alpha \subseteq E_{\dom \alpha}$.}
Given $\tau\in\Z^+$, $\alpha$ is \emph{$\tau$-stable} if every cut of $\bindinggraph_\alpha$ has weight at least $\tau$, where the weight of an edge is the strength of the glue it represents.
That is, $\alpha$ is $\tau$-stable if at least energy $\tau$ is required to separate $\alpha$ into two parts.
When $\tau$ is clear from context, we say $\alpha$ is \emph{stable}.






\opt{submission}{\paragraph{Seeded aTAM.}}
\opt{normal}{\subsection{Seeded aTAM}}
A \emph{seeded tile assembly system} (seeded TAS) is a triple $\calT = (T,\sigma,\tau)$, where $T$ is a finite set of tile types, $\sigma:\Z^2 \dashrightarrow T$ is the finite, $\tau$-stable \emph{seed assembly},
%$g:\Lambda(T)\to\N$ is the \emph{strength function},
and $\tau\in\Z^+$ is the \emph{temperature}.
Let $|\calT|$ denote $|T|$.
If $\calT$ has a single seed tile $s\in T$ (i.e., $\sigma(0,0)=s$ for some $s \in T$ and is undefined elsewhere), then we write $\calT=(T,s,\tau).$
Given two $\tau$-stable assemblies $\alpha,\beta:\Z^2 \dashrightarrow T$, we write $\alpha \to_1^{\calT} \beta$ if $\alpha \sqsubseteq \beta$ and $|\dom \beta \setminus \dom \alpha| = 1$. In this case we say $\alpha$ \emph{$\calT$-produces $\beta$ in one step}.\footnote{Intuitively $\alpha \to_1^\calT \beta$ means that $\alpha$ can grow into $\beta$ by the addition of a single tile; the fact that we require both $\alpha$ and $\beta$ to be $\tau$-stable implies in particular that the new tile is able to bind to $\alpha$ with strength at least $\tau$. It is easy to check that had we instead required only $\alpha$ to be $\tau$-stable, and required that the cut of $\beta$ separating $\alpha$ from the new tile has strength at least $\tau$, then this implies that $\beta$ is also $\tau$-stable.}
If $\alpha \to_1^{\calT} \beta$, $ \dom \beta \setminus \dom \alpha=\{p\}$, and $t=\beta(p)$, we write $\beta = \alpha + (p \mapsto t)$.
%The \emph{$\calT$-frontier} of $\alpha$ is the set $\partial^\calT \alpha = \bigcup_{\alpha \to_1^\calT \beta} \dom \beta \setminus \dom \alpha$, the set of empty locations at which a tile could stably attach to $\alpha$.
%The \emph{$t$-frontier} $\partial_t \alpha \subseteq \partial \alpha$ of $\alpha$ is the set $\setr{p\in\partial \alpha}{\alpha \to_1^\calT \beta \text{ and } \beta(p)=t}.$

A sequence of $k\in\Z^+$ % \cup \{\infty\}$ 
assemblies $\vec{\alpha} = (\alpha_0,\alpha_1,\ldots,\alpha_{k-1})$ is a \emph{$\calT$-assembly sequence} if, for all $1 \leq i < k$, $\alpha_{i-1} \to_1^\calT \alpha_{i}$.
We write $\alpha \to^\calT \beta$, and we say $\alpha$ \emph{$\calT$-produces} $\beta$ (in 0 or more steps) if there is a $\calT$-assembly sequence $\vec{\alpha}=(\alpha,\alpha_1,\alpha_2,\ldots,\alpha_{k-1} = \beta)$ of length $k = |\dom \beta \setminus \dom \alpha| + 1$. %such that
%1) $\alpha = \alpha_0$,
%2) $\dom \beta = \bigcup_{0 \leq i < k} \dom {\alpha_i}$, and
%3) for all $0 \leq i < k$, $\alpha_{i} \sqsubseteq \beta$.
%In this case, we say that $\beta$ is the \emph{result} of $\vec{\alpha}$, written $\beta=\res{\vec{\alpha}}$.
%If $k$ is finite then it is routine to verify that $\res{\vec{\alpha}} = \alpha_{k-1}$.\footnote{If we had defined the relation $\to^\calT$ based on only finite assembly sequences, then $\to^\calT$ would be simply the reflexive, transitive closure $(\to_1^\calT)^*$ of $\to_1^\calT$. But this would mean that no infinite assembly could be produced from a finite assembly, even though there is a well-defined, unique ``limit assembly'' of every infinite assembly sequence.}
%We assume only finite assembly sequences in this paper.
We say $\alpha$ is \emph{$\calT$-producible} if $\sigma \to^\calT \alpha$, and we write $\prodasm{\calT}$ to denote the set of $\calT$-producible assemblies.
The relation $\to^\calT$ is a partial order on $\prodasm{\calT}$ \cite{Roth01,jSSADST}. %\footnote{In fact it is a partial order on the set of $\tau$-stable assemblies, including even those that are not $\calT$-producible.}
%Note that all $\calT$-producible assemblies are $\tau$-stable.
%A $\calT$-assembly sequence $\alpha_0,\alpha_1,\ldots$ is \emph{fair} if, for all $i$ and all $p\in\partial^\calT\alpha_i$, there exists $j$ such that $\alpha_j(p)$ is defined; i.e., no frontier location is ``starved''.

%Given a TAS $\calT=(T,\sigma,\tau)$, an assembly $\alpha$ is \emph{$\calT$-producible}, or \emph{producible} if $\calT$ is clear from context, if either $\alpha = \sigma$, or $\alpha$ results from the $\tau$-stable attachment of a single tile to a producible assembly (``$\tau$-stable attachment'' meaning that the cut separating the tile from the rest of the assembly has strength $\geq \tau$, which implies by induction that $\alpha$ is $\tau$-stable).
An assembly $\alpha$ is \emph{$\calT$-terminal} if $\alpha$ is $\tau$-stable and $\partial^\calT \alpha=\emptyset$.
%It is easy to check that an assembly sequence $\vec{\alpha}$ is fair if and only $\res{\vec{\alpha}}$ is terminal.
We write $\termasm{\calT} \subseteq \prodasm{\calT}$ to denote the set of $\calT$-producible, $\calT$-terminal assemblies.

A seeded TAS $\calT$ is \emph{directed (a.k.a., deterministic, confluent)} if the poset $(\prodasm{\calT}, \to^\calT)$ is directed; i.e., if for each $\alpha,\beta \in \prodasm{\calT}$, there exists $\gamma\in\prodasm{\calT}$ such that $\alpha \to^\calT \gamma$ and $\beta \to^\calT \gamma$.\footnote{The following two convenient characterizations of ``directed'' are routine to verify.
$\calT$ is directed if and only if $|\termasm{\calT}| = 1$.
$\calT$ is \emph{not} directed if and only if there exist $\alpha,\beta\in\prodasm{\calT}$ and $p \in \dom \alpha \cap \dom \beta$ such that $\alpha(p) \neq \beta(p)$.}
We say that $\calT$ \emph{uniquely produces} $\alpha$ if $\termasm{\calT} = \{\alpha\}$.
%We say that a TAS $\calT$ \emph{strictly self-assembles} a shape $S \subseteq \Z^2$ if, for all $\alpha \in \termasm{\calT}$, $\dom \alpha = S$; i.e., if every terminal assembly produced by $\calT$ has shape $S$.
%If $\calT$ strictly self-assembles some shape $S$, we say that $\calT$ is \emph{strict}.
%Note that the implication ``$\calT$ is directed $\implies$ $\calT$ is strict'' holds, but the converse does not hold.


\opt{submission}{\paragraph{Hierarchical aTAM.}}
\opt{normal}{\subsection{Hierarchical aTAM}}
A \emph{hierarchical tile assembly system} (hierarchical TAS) is a pair $\calT = (T,\tau)$, where $T$ is a finite set of tile types,
%$g:\Lambda(T)\to\N$ is the \emph{strength function},
and $\tau\in\Z^+$ is the \emph{temperature}.
Let $\alpha,\beta:\Z^2 \dashrightarrow T$ be two assemblies.
Say that $\alpha$ and $\beta$ are \emph{nonoverlapping} if $\dom\alpha \cap \dom\beta = \emptyset$.
If $\alpha$ and $\beta$ are nonoverlapping assemblies, define $\alpha \cup \beta$ to be the assembly $\gamma$ defined by $\gamma(p) = \alpha(p)$ for all $p\in\dom\alpha$, $\gamma(p) = \beta(p)$ for all $p \in \dom \beta$, and $\gamma(p)$ is undefined for all $p \in \Z^2 \setminus (\dom\alpha \cup \dom\beta)$.
An assembly $\gamma$ is \emph{singular} if $\gamma(p)=t$ for some $p\in\Z^2$ and some $t \in T$ and $\gamma(p')$ is undefined for all $p' \in \Z^2 \setminus \{p\}$.
Given a hierarchical TAS $\calT=(T,\tau)$, an assembly $\gamma$ is \emph{$\calT$-producible} if either 1) $\gamma$ is singular, or 2) there exist producible nonoverlapping assemblies $\alpha$ and $\beta$ such that $\gamma = \alpha\cup\beta$ and $\gamma$ is $\tau$-stable. %\footnote{Unlike some definitions of the hierarchical aTAM, we have not allowed for translation of $\alpha$ and $\beta$ to determine whether they can stably attach.  This is because every translation of every producible assembly is itself producible.}
In the latter case, write $\alpha + \beta \to_1^\calT \gamma$.
An assembly $\alpha$ is \emph{$\calT$-terminal} if for every producible assembly $\beta$ such that $\alpha$ and $\beta$ are nonoverlapping, $\alpha \cup \beta$ is not $\tau$-stable.\footnote{The restriction on overlap is a model of a chemical phenomenon known as \emph{steric hindrance}~\cite[Section 5.11]{WadeOrganicChemistry91} or, particularly when employed as a design tool for intentional prevention of unwanted binding in synthesized molecules, \emph{steric protection}~\cite{HellerPugh1,HellerPugh2,GotEtAl00}.}
Define $\prodasm{\calT}$ to be the set of all $\calT$-producible assemblies.
Define $\termasm{\calT} \subseteq \prodasm{\calT}$ to be the set of all $\calT$-producible, $\calT$-terminal assemblies.
A hierarchical TAS $\calT$ is \emph{directed (a.k.a., deterministic, confluent)} if $|\termasm{\calT}|=1$. %\footnote{Again, technically by this we mean that the quotient set of $\termasm{\calT}$ under the equivalence relation defined by equality under translation is a singleton set.}
We say that $\calT$ \emph{uniquely produces} $\alpha$ if $\termasm{\calT} = \{\alpha\}$.
%We say that a TAS $\calT$ \emph{strictly self-assembles} a shape $S \subseteq \Z^2$ if, for all $\alpha \in \termasm{\calT}$, $\dom \alpha = S$; i.e., if every terminal assembly produced by $\calT$ has shape $S$.

Let $\calT$ be a hierarchical TAS, and let $\widehat{\alpha} \in \prodasm{\calT}$ be a $\calT$-producible assembly.
An \emph{assembly tree} $\Upsilon$ of $\widehat{\alpha}$ is a full binary tree with $|\widehat{\alpha}|$ leaves, whose nodes are labeled by $\calT$-producible assemblies, with $\widehat{\alpha}$ labeling the root, singular assemblies labeling the leaves, and node $u$ labeled with $\gamma$ having children $u_1$ labeled with $\alpha$ and $u_2$ labeled with $\beta$, with the requirement that $\alpha + \beta \to_1^\calT \gamma$.
That is, $\Upsilon$ represents one possible pathway through which $\widehat{\alpha}$ could be produced from individual tile types in $\calT$.
Let $\Upsilon(\calT)$ denote the set of all assembly trees of $\calT$.
If $\alpha$ is a descendant node of $\beta$ in an assembly tree of $\calT$, write $\alpha \to^\calT \beta$.
Say that an assembly tree is \emph{$\calT$-terminal} if its root is a $\calT$-terminal assembly.
Let $\Upsilon_\Box(\calT)$ denote the set of all $\calT$-terminal assembly trees of $\calT$.
Note that even a directed hierarchical TAS can have multiple terminal assembly trees that all have the same root terminal assembly.




%In this paper we will always use \emph{singly-seeded temperature-2} TAS's, those with $| \sigma|=1$ and $\tau=2$; hence we will use the term \emph{seed tile} for $\sigma$ as well, and for the remainder of this paper we use the term TAS to mean singly-seeded temperature-2 TAS.
When $\calT$ is clear from context, we may omit $\calT$ from the notation above and instead write
$\to_1$,
$\to$,
$\partial \alpha$,
%\emph{frontier},
\emph{assembly sequence},
\emph{produces},
\emph{producible}, and
\emph{terminal}.
%Since the behavior of a TAS $\calT=(T,\sigma,2)$ is unchanged if every glue with strength greater than 2 is changed to have strength exactly 2, we assume henceforth that all glue strengths are 0, 1, or 2, and use the terms \emph{null glue}, \emph{single glue}, and \emph{double glue}, respectively, to refer to these three cases.\footnote{We use \emph{null bond}, \emph{single bond}, and \emph{double bond} similarly to refer to the \emph{interaction} of two tiles.}
%We also assume without loss of generality that every positive-strength glue occurring in some tile type in some direction also occurs in some tile type in the opposite direction, i.e., there are no ``effectively null'' positive-strength glues.
%We also assume without loss of generality that every single glue or double glue occurring in some tile type in some direction also occurs in some tile type in the opposite direction, i.e., there are no ``effectively null'' single or double glues.
%\footnote{Thus the existence of a tile with a double glue facing empty space implies that the empty space is part of the frontier. Many of our arguments use the contrapositive that if a shape $S$ is strictly self-assembled by a tile assembly system and a side of a tile faces a point $p \not\in S$, then the tile cannot have a double glue on that side.}



tam-informal.tex
\section{Informal definition of the abstract tile assembly model}
\label{sec-tam-informal}

This section gives a brief informal sketch of the seeded and hierarchical variants of the abstract Tile Assembly Model (aTAM).
%See~\cite{RotWin00} for a formal definition of the standard aTAM and~\cite{AGKS05,DotPatReiSchSum10} for a formal definition of the hierarchical aTAM.
See Section \ref{sec-tam-formal} for a formal definition of the aTAM.

A \emph{tile type} is a unit square with four sides, each consisting of a \emph{glue label} (often represented as a finite string) and a nonnegative integer \emph{strength}.
We assume a finite set $T$ of tile types, but an infinite number of copies of each tile type, each copy referred to as a \emph{tile}.
If a glue has strength 0, we say it is \emph{null}, and if a positive-strength glue facing some direction does not appear on some tile type in the opposite direction, we say it is \emph{functionally null}.
We assume that all tile sets in this paper contain no functionally null glues.
An \emph{assembly}
%(a.k.a., \emph{supertile})
is a positioning of tiles on the integer lattice $\Z^2$; i.e., a partial function $\alpha:\Z^2 \dashrightarrow T$. %(more formally an equivalence class of all translations of a given assembly).
We write $|\alpha|$ to denote $|\dom \alpha|$.
Write $\alpha \sqsubseteq \beta$ to denote that $\alpha$ is a \emph{subassembly} of $\beta$, which means that $\dom\alpha \subseteq \dom\beta$ and $\alpha(p)=\beta(p)$ for all points $p\in\dom\alpha$.
In this case, say that $\beta$ is a \emph{superassembly} of $\alpha$.
We abuse notation and take a tile type $t$ to be equivalent to the single-tile assembly containing only $t$ (at the origin if not otherwise specified).
%For a set of tile types $T$, let $\Lambda(T)$ denote the set of all glue labels of tile types in $T$.
%A \emph{strength function} is a function $g:\Lambda(T)\to\N$ indicating, for each glue label $\ell$, the strength $str(\ell)$ with which it binds.
Two adjacent tiles in an assembly \emph{interact} if the glue labels on their abutting sides are equal and have positive strength. %according to $g$.
Each assembly induces a \emph{binding graph}, a grid graph whose vertices are tiles, with an edge between two tiles if they interact.
The assembly is \emph{$\tau$-stable} if every cut of its binding graph has strength at least $\tau$, where the weight of an edge is the strength of the glue it represents.
%That is, the assembly is stable if at least energy $\tau$ is required to separate the assembly into two parts.
%The \emph{frontier} $\partial\alpha \subseteq \Z^2 \setminus \dom\alpha$ of $\alpha$ is the set of empty locations adjacent to $\alpha$ at which a single tile could bind stably.

A \emph{seeded tile assembly system} (seeded TAS) is a triple $\calT = (T,\sigma,\tau)$, where $T$ is a finite set of tile types, $\sigma:\Z^2 \dashrightarrow T$ is a finite, $\tau$-stable \emph{seed assembly}, %$g:\Lambda(T) \to \N$ is the \emph{strength function},
and $\tau$ is the \emph{temperature}.
If $\calT$ has a single seed tile $s\in T$ (i.e., $\sigma(0,0)=s$ for some $s \in T$ and is undefined elsewhere), then we write $\calT=(T,s,\tau).$
Let $|\calT|$ denote $|T|$.
%Given a seeded TAS $\calT = (T,\sigma,\tau)$,
An assembly $\alpha$ is \emph{producible} if either $\alpha = \sigma$ or if $\beta$ is a producible assembly and $\alpha$ can be obtained from $\beta$ by the stable binding of a single tile.
%placing a single tile type $t$ on
%empty space (a position $p\in\Z^2$ such that $\beta(p)$ is undefined), such that the resulting assembly $\alpha$ is $\tau$-stable.
In this case write $\beta\to_1 \alpha$ ($\alpha$ is producible from $\beta$ by the attachment of one tile), and write $\beta\to \alpha$ if $\beta \to_1^* \alpha$ ($\alpha$ is producible from $\beta$ by the attachment of zero or more tiles).
An assembly is \emph{terminal} if no tile can be $\tau$-stably attached to it.

%\missingfigure{Show example of hierarchical model.}
A \emph{hierarchical tile assembly system} (hierarchical TAS) is a pair $\calT = (T,\tau)$, where $T$ is a finite set of tile types and $\tau \in \N$ is the temperature.
%Given a hierarchical TAS $\calT=(T,\tau)$,
An assembly is \emph{producible} if either it is a single tile from $T$, or it is the $\tau$-stable result of translating two producible assemblies without overlap.
Therefore, if an assembly $\alpha$ is producible, then it is produced via an \emph{assembly tree}, a full binary tree whose root is labeled with $\alpha$, whose $|\alpha|$ leaves are labeled with tile types, and each internal node is a producible assembly formed by the stable attachment of its two child assemblies.
An assembly $\alpha$ is \emph{terminal} if for every producible assembly $\beta$, $\alpha$ and $\beta$ cannot be $\tau$-stably attached.
%The restriction on overlap is a model of a chemical phenomenon known as \emph{steric hindrance}~\cite[Section 5.11]{WadeOrganicChemistry91} or, particularly when employed as a design tool for intentional prevention of unwanted binding in synthesized molecules, \emph{steric protection}~\cite{HellerPugh1,HellerPugh2,GotEtAl00}.
If $\alpha$ can grow into $\beta$ by the attachment of zero or more assemblies, then we write $\alpha \to \beta$.

Note that our definitions imply only finite assemblies are producible.
In either the seeded or hierarchical model, let $\prodasm{\calT}$ be the set of producible assemblies of $\calT$, and let $\termasm{\calT} \subseteq \prodasm{\calT}$ be the set of producible, terminal assemblies of $\calT$.
A TAS $\calT$ is \emph{directed} (a.k.a., \emph{deterministic}, \emph{confluent}) if $|\termasm{\calT}| = 1$.
If $\calT$ is directed with unique producible terminal assembly $\alpha$, we say that $\calT$ \emph{uniquely produces} $\alpha$.
It is easy to check that in the seeded aTAM, $\calT$ uniquely produces $\alpha$ if and only if every producible assembly $\beta \sqsubseteq \alpha$.
%
In the hierarchical model, a similar condition holds, although it is more complex since hierarchical assemblies, unlike seeded assemblies, do not have a ``canonical translation'' defined by the seed.
$\calT$ uniquely produces $\alpha$ if and only if for every producible assembly $\beta$, there is a translation $\beta'$ of $\beta$ such that $\beta' \sqsubseteq \alpha$.
In particular, if there is a producible assembly $\beta \neq \alpha$ such that $\dom \alpha = \dom \beta$, then $\alpha$ is not uniquely produced.
Since $\dom \beta = \dom \alpha$, every nonzero translation of $\beta$ has some tiled position outside of $\dom \alpha$, whence no such translation can be a subassembly of $\alpha$, implying $\alpha$ is not uniquely produced.


%Given a connected shape $X \subseteq \Z^2$,  a TAS $\calT$ \emph{strictly self-assembles $S$}  if every producible, terminal assembly places tiles exactly on those positions in $X$.
% (appropriately translated if necessary).
%We say that $\calT$ \emph{uniquely self-assembles} $X$ (a.k.a., \emph{produces $X$ uniquely}) if $\calT$ strictly self-assembles $X$ and $\calT$ is directed.


union.tex
﻿\section{Unions of producible assemblies are producible}
\label{sec-union}

Throughout this section, fix a hierarchical TAS $\calT=(T,\tau)$.
Let $\alpha,\beta$ be assemblies.
We say $\alpha$ and $\beta$ are \emph{consistent} if $\alpha(p) = \beta(p)$ for all points $p \in \dom \alpha \cap \dom \beta$.
If $\alpha$ and $\beta$ are consistent, let $\alpha \cup \beta$ be defined as the assembly $(\alpha\cup\beta)(p) = \alpha(p)$ if $\alpha$ is defined, and $(\alpha\cup\beta)(p)=\beta(p)$ if $\alpha(p)$ is undefined.
If $\alpha$ and $\beta$ are not consistent, let $\alpha \cup \beta$ be undefined.

\begin{thm} \label{thm-union-producible}
  If $\alpha,\beta$ are producible assemblies that are consistent and $\dom\alpha \cap \dom\beta \neq \emptyset$, then $\alpha \cup \beta$ is producible.
  Furthermore, $\alpha \to \alpha \cup \beta$, i.e., it is possible to assemble exactly $\alpha$, then to assemble the missing portions of $\beta$.
\end{thm}


\begin{proof}
  If $\alpha$ and $\beta$ are consistent and have non-empty overlap, then $\alpha \cup \beta$ is necessarily stable, since every cut of $\alpha \cup \beta$ is a superset of some cut of either $\alpha$ or $\beta$, which are themselves stable.

    \begin{figure}[htb]
    \centering
      \subfigure
        [{\figuresize First operation to combine the assembly trees for $\alpha$ and $\beta$.  $l_1$ and $l_2$ are two leaves representing the same position in $\dom \alpha \cap \dom \beta$.}]{
        \includegraphics[width=3in]{figures/tree-surgery-first-step}
        \label{fig:tree-surgery-first-step}
      }
      \hfill
      %\caption{\label{fig:tree-surgery-first-step} \figuresize
      %First operation to combine the assembly trees for $\alpha$ and $\beta$.  $l_1$ and $l_2$ are two leaves representing the same position in $\dom \alpha \cap \dom \beta$, and $p_2$ is the parent of $l_2$.}
      \subfigure
        [{\figuresize Operation to eliminate one of two leaves $l_1$ and $l_2$ representing the same tile in the tree while preserving that all attachments are stable.}]{
        \includegraphics[width=3in]{figures/tree-surgery}
        \label{fig:tree-surgery}
      }
      %\caption{\label{fig:tree-surgery-first-step} \figuresize
      %First operation to combine the assembly trees for $\alpha$ and $\beta$.  $l_1$ and $l_2$ are two leaves representing the same position in $\dom \alpha \cap \dom \beta$, and $p_2$ is the parent of $l_2$.}
      \label{fig:tree-surgery-whole}
      \caption{Procedure to construct assembly tree for $\alpha \cup \beta$ from separate assembly trees for $\alpha$ and $\beta$.}
    \end{figure}

  %Let $O = \dom\alpha \cap \dom\beta$ be the region of overlap of $\alpha$ and $\beta$.
  %Let $\gamma = \alpha \upharpoonright O$ be the assembly in this region.
  Let $\Ua$ and $\Ub$ be assembly trees for $\alpha$ and $\beta$, respectively.
  Define an assembly tree $\U$ for $\alpha \cup \beta$ by the following construction.
  Let $l_1$ be a leaf in $\Ua$ and let $l_2$ be a leaf in $\Ub$ representing the same position $x \in \dom\alpha \cap \dom\beta$, as shown in Figure~\ref{fig:tree-surgery-first-step}.
  Remove $l_2$ and replace it with the entire tree $\Ua$.
  Call the resulting tree $\U'$.
  At this point, $\U'$ is not an assembly tree if $\alpha$ and $\beta$ overlapped on more than one point, because every position in $\dom\alpha \cap \dom\beta \setminus \{x\}$ has duplicated leaves.
  Therefore the tree $\U'$ is not a hierarchical division of the set $\dom \alpha \cup \dom \beta$, since not all unions represented by each internal node are disjoint unions.
  However, each such union does represent a stable assembly.
  We will show how to modify $\U'$ to eliminate each of these duplicates, while maintaining the invariant that each internal node represents a stable attachment, and we call the resulting assembly tree $\U$.
  Furthermore, the subtree $\Ua$ that was placed under $p_2$ will not change as a result of these modifications, which implies $\alpha \to \alpha \cup \beta$.


    %\begin{figure}[htb]
%    \begin{center}
%      \includegraphics[width=4in]{figures/tree-surgery}
%      \caption{\label{fig:tree-surgery} \figuresize
%      Operation to eliminate one of two leaves $l_1$ and $l_2$ representing the same tile in the tree while preserving that all attachments are stable.
%      }
%    \end{center}
%    \end{figure}

  The process to eliminate one pair of duplicate leaves is shown in Figure \ref{fig:tree-surgery}.
  Let $l_1$ and $l_2$ be two leaves representing the same point in $\dom\alpha \cap \dom\beta$, and let $a$ be their least common ancestor in $\U$, noting that $a$ is not contained in $\Ua$ since $l_2$ is not contained in $\Ua$.
  Let $p_a$ be the parent of $a$.
  Let $r_1$ be the root of the subtree under $a$ containing $l_1$.
  Let $r_2$ be the root of the subtree under $a$ containing $l_2$.
  Let $p_2$ be the parent of $l_2$.
  Remove the leaf $l_2$ and the node $a$.
  Set the parent of $r_1$ to be $p_2$.
  Set the parent of $r_2$ to be $p_a$.

  Since we have replaced the leaf $l_2$ with a subtree containing the leaf $l_1$, the subtree rooted at $r_1$ is an assembly containing the tile represented by $l_2$, in the same position.
  Since the original attachment of $l_2$ to its sibling was stable, by monotonicity, the attachment represented by $p_2$ is still legal.
  The removal of $a$ is simply to maintain that $\Upsilon$ is a full binary tree; leaving it would mean that it represents a superfluous ``attachment'' of the assembly $r_2$ to $\emptyset$.
  However, it is now legal for $r_2$ to be a direct child of $p_a$, since $r_2$ (due to the insertion of the entire $r_1$ subtree beneath a descendant of $r_2$, again by monotonicity) now has all the tiles necessary for its attachment to the old sibling of $a$ to be stable.
  Since $a$ was not contained in $\Ua$, the subtree $\Ua$ has not been altered.

  This process is iterated for all duplicate leaves.
  When all duplicates have been removed, $\Upsilon$ is a valid assembly tree with root $\alpha \cup \beta$. %, testifying that $\alpha \cup \beta$ is producible.
  Since $\Upsilon$ contains $\Ua$ as a subtree, $\alpha \to \alpha \cup \beta$.
\end{proof}



upv-t1.tex
﻿\section{Linear-time verification of temperature 1 unique production}
\label{sec-upv-t1}

This section shows that there is an algorithm, faster than the previous known algorithm~\cite{TwoHandsBetterThanOne}, that solves the temperature 1 \emph{unique producibility verification} (UPV) problem: given an assembly $\alpha$ and a temperature-1 hierarchical tile system $\calT$, decide if $\alpha$ is the unique producible, terminal assembly of $\calT$.
This is done by showing an algorithm for the temperature 1 UPV problem in the seeded model (which is faster than the general-temperature algorithm of~\cite{ACGHKMR02}), and then applying the technique of~\cite{TwoHandsBetterThanOne} relating producibility and terminality in the temperature 1 seeded and hierarchical models.

%We actually give two independent algorithms.
%One is based on showing an improved algorithm for the UPV problem in the seeded model, and then apply the technique of~\cite{TwoHandsBetterThanOne} relating producibility and terminality in the seeded and hierarchical models.
%We then show a simpler direct algorithm for the hierarchical model.
%We include the former algorithm because the employed algorithm for the seeded model may be of independent interest.

Define the decision problems $\sUPV$ and $\hUPV$ by the language $\setr{(\calT,\alpha)}{\termasm{\calT} = \{\alpha\}},$ where $\calT$ is a temperature 1 seeded TAS in the former case and a temperature 1 hierarchical TAS in the latter case.
To simplify the time analysis we assume $|\calT| = O(|\alpha|)$.


%\subsection{Reducing $\hUPV$ to $\sUPV$}


%The following theorem shows an efficient algorithm for the $\sUPV$ problem.
The following is the only result in this paper on the seeded aTAM.

\begin{thm}\label{thm-alg-temp1-seeded}
  There is an algorithm that solves the $\sUPV$ problem in time $O(|\alpha| \log |\calT|)$.
\end{thm}

\begin{proof}
%\todo{Check that every tile type in $\alpha$ actually appears in $\calT$ and update running time accordingly.}
    Let $\calT=(T,s,1)$ and $\alpha$ be a instance of the $\sUPV$ problem.
    We first check that every tile in $\alpha$ appears in $T$, which can be done in time $O(|\alpha| \log |T|)$ by storing elements of $T$ in a data structure supporting $O(\log n)$ time access.
    In the seeded aTAM at temperature 1, $\alpha$ is producible if and only if it contains the seed $s$ and its binding graph is connected, which can be checked in time $O(|\alpha|)$.
    We must also verify that $\alpha$ is terminal, which is true if and only if all glues on unbound sides are null, checkable in time $O(|\alpha|)$.

    Once we have verified that $\alpha$ is producible and terminal, it remains to verify that $\calT$ uniquely produces $\alpha$. %, which is true if there is no producible assembly $\beta$ that is inconsistent with $\alpha$, i.e., such that $\alpha(p) \neq \beta(p)$ for some $p\in\dom \alpha \cap \dom \beta$.
    Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espan\'{e}s, and Rothemund~\cite{ACGHKMR02} showed that this is true (at any temperature) if and only if, for every position $p \in \dom\alpha$, if $\alpha_p \sqsubset \alpha$ is the maximal producible subassembly of $\alpha$ such that $p \not \in \dom \alpha_p$, then $\alpha(p)$ is the only tile type attachable to $\alpha_p$ at position $p$.
    They solve the problem by producing each such $\alpha_p$ and checking whether there is more than one tile type attachable to $\alpha_p$ at $p$.
    We use a similar approach, but we avoid producing each $\alpha_p$ by exploiting special properties of temperature 1 producibility.


    %We simplify the process at temperature 1 by using the fact that an assembly is producible if and only if it is stable (its binding graph is connected) and contains the seed.
    Given $p,q\in\dom\alpha$ such that $p \neq q$, write $p \prec q$ if, for every producible assembly $\beta$, $q \in \dom \beta \implies p \in \dom \beta$, i.e., the tile at position $p$ must be present before the tile at position $q$ can be attached.
    We must check each $p \in\dom \alpha$ and each position $q\in\dom\alpha$ adjacent to $p$ such that $p \not \prec q$ to see whether a tile type $t \neq \alpha(p)$ shares a positive-strength glue with $\alpha(q)$ in direction $q-p$ (i.e., whether, if $\alpha(p)$ were not present, $t$ could attach at $p$ instead).
    If we know which positions $q$ adjacent to $p$ satisfy $p \not\prec q$, this check can be done in time $O(\log |T|)$ with appropriate choice of data structure, implying total time $O(|\alpha| \log |T|)$ over all positions $p \in \dom \alpha$.
    It remains to show how to determine which adjacent positions $p,q \in \dom \alpha$ satisfy $p \prec q$.

    Recall that a \emph{cut vertex} of a connected graph is a vertex whose removal disconnects the graph, and that a subgraph is \emph{biconnected} if the removal of any single vertex from the subgraph leaves it connected.
    Every graph can be decomposed into a tree of biconnected components, with cut vertices connecting different biconnected components (and belonging to all biconnected components that they connect).
    If $p$ is not a cut vertex of the binding graph of $\alpha$, then $\dom \alpha_p$ is simply $\dom \alpha \setminus \{p\}$ because, for all $q \in \dom \alpha \setminus \{p\}$, $p \not\prec q$.
    If $p$ is a cut vertex, then $p \prec q$ if and only if 
    %$q$ and the seed position are in different biconnected components of the biconnected decomposition of the binding graph, i.e., if and only if 
    removing $p$ from the binding graph of $\alpha$ places $q$ and the seed position in two different connected components.
    This is because the connected component containing the seed after removing $p$ corresponds precisely to $\alpha_p$.

    %Check in time $O(\alpha)$ that there are no adjacent tiles $t_1$ and $t_2$ that have mismatching positive-strength glues.
%    If so, then there is a path from $s$ to one of the tiles -- assume without loss of generality it is $t_1$ -- that does not contain the other.
%    Then there is a producible assembly (containing only this path) with $t_1$ and not $t_2$, meaning that the tile type $t_3 \neq t_2$ matching $t_1$'s glue can be placed in $t_2$'s position, implying a producible assembly $\beta$ inconsistent with $\alpha$.
%    If no such pair exists, then for every other remaining mismatch, one of the mismatching glues is null.
%
%    For tiles $t_1$ and $t_2$ adjacent in $\alpha$ such that $t_2$ has a positive-strength glue mismatching $t_1$'s null glue, this mismatch implies nondeterminism if and only if (because this is temperature 1) there is a path from $s$ to $t_2$ that does not contain $t_1$.
%    In other words, if this condition holds, then it would have been possible to put a different tile in place of $t_1$ by growing a path not containing $t_1$ from $s$ to $t_2$ and then placing the neighbor that $t_2$ ``wanted'' to place instead of $t_1$.
%    The mismatch does \emph{not} imply nondeterminism if $t_1$ is a \emph{cut vertex} (one whose removal disconnects the graph) that separates $s$ and $t_2$ into different connected components if $t_1$ is removed.
%    In this case, all paths from $s$ to $t_2$ go through $t_1$, so it is not possible to place $t_2$ without placing $t_1$, meaning it is not possible for $t_2$'s mismatching glue facing $t_1$ to place a competing tile in the position $t_1$ occupies in $\alpha$.

    Run the linear time Hopcroft-Tarjan algorithm~\cite{HopcroftTarjanBiconnected73} for decomposing the binding graph of $\alpha$ into a tree of its biconnected components, which also identifies which vertices in the graph are cut vertices and which biconnected components they connect.
    Recall that the Hopcroft-Tarjan algorithm is an augmented depth-first search.
    Root the tree with $s$'s biconnected component (i.e., start the depth-first search there), so that each component has a parent component and child components.
    In particular, each cut vertex $p$ has a ``parent'' biconnected component and $k \geq 1$ ``child'' biconnected components.
    %In particular, each component $C$ has a cut vertex $p$ connecting to the parent component $P$ of $C$; call $p$ the ``parent vertex'' of $C$.
    %$C$ also has a number of cut vertices leading to its child components that we call ``child vertices.''
    %When we say, ``the subtree rooted at $p$,'' if $p$ is not a cut vertex, then this means, ``the subtree rooted at the parent vertex of the component in which $p$ is contained,'' and if $p$ is a cut vertex, then this means ``the subtree rooted at $p$.''
    Removing such a cut vertex $p$ will separate the graph into $k+1$ connected components: the nodes in the $k$ subtrees and the remaining nodes connected to the parent biconnected component of $p$.
    Thus $p \prec q$ if and only if $p$ is a cut vertex and $q$ is contained in the subtree rooted at $p$.
    %Thus every path from $s$ to a vertex $u$ goes through $v$ if and only if $v$ is a cut vertex and $u$ is contained in a subtree of $v$.

    %Check whether the mismatch between $t_1$ and $t_2$ implies nondeterminism, using the information gained from the biconnected decomposition, as follows.
%    If $t_1$ is not a cut vertex, then the mismatch implies nondeterminism since every node of the binding graph (including $t_2$) is reachable from $s$ without passing through $t_1$.
%    If $t_1$ is a cut vertex, then the mismatch implies nondeterminism if and only if $t_2$ is not contained in the subtree under $t_1$, since $t_2$ is contained in $t_1$'s subtree if and only if every path from $s$ to $t_2$ must pass through $t_1$.

    This check can be done for all positions $p$ and their $\leq 4$ adjacent positions $q$ in linear time by ``weaving'' the checks into the Hopcroft-Tarjan algorithm.
    As the depth-first search executes, each vertex $p$ is marked as either \emph{unvisited}, \emph{visiting} (meaning the search is currently in a subtree rooted at $p$), or \emph{visited} (meaning the search has visited and exited the subtree rooted at $p$).
    If $p$ is marked as visited or unvisited at the time $q$ is processed, then $q$ is not in the subtree under $p$. %, so the algorithm rejects. %there is a path from $s$ to $t_2$ not passing through $t_1$.
    If $p$ is marked as visiting when $q$ is processed, then $q$ is in $p$'s subtree. %, so the algorithm continues. %thus if $t_1$ is a cut vertex, all paths from $s$ to $t_2$ contain $t_1$.

    At the time $q$ is visited, it may not yet be known whether $p$ is a cut vertex.
    %The identity of each vertex's biconnected component, and whether the vertex is a cut vertex or not, may not be available at the time the vertex is processed.
    To account for this, simply run the Hopcroft-Tarjan algorithm twice, doing the checks just described on the second execution, using the cut vertex information obtained on the first execution.
\end{proof}

\begin{thm}\label{thm-alg-temp1-hier}
  There is an algorithm that solves the $\hUPV$ problem in time $O(|\alpha| |\calT| \log |\calT|)$.
\end{thm}

\begin{proof}
  Cannon, Demaine, Demaine, Eisenstat, Patitz, Schweller, Summers, and Winslow~\cite{TwoHandsBetterThanOne} showed that a temperature 1 hierarchical TAS $\calT=(T,1)$ uniquely produces $\alpha$ if and only if, for each $s \in T$, the seeded TAS $\calT_s = (T,s,1)$ uniquely produces $\alpha$.
  Therefore, the $\hUPV$ problem can be solved by calling the algorithm of Theorem~\ref{thm-alg-temp1-seeded} $|\calT|$ times, resulting in a running time of $O(|\alpha| |\calT| \log |\calT|)$.
  %The preprocessing step that accounts for the $|\alpha| \log |\calT|$ term in the running time of the algorithm of Theorem~\ref{thm-alg-temp1-seeded} -- checking that each tile type in $\alpha$ appears in $T$ -- needs to be done only once.
  %The remainder of that algorithm takes time $O(|\alpha|)$, which we execute $|\calT|$ times.
  %Therefore the total running time over all $s \in T$ is $O(|\calT| \cdot |\alpha| + |\alpha| \log |\calT|) = O(|\calT| \cdot |\alpha|)$.
\end{proof}














\begin{comment}

\subsection{Direct algorithm for $\hUPV$}
We now show that there is a more direct algorithm for deciding $\hUPV$, which is faster than that described in Theorem~\ref{thm-alg-temp1-hier}.
Let $\calT=(T,1)$ be a temperature 1 hierarchical TAS.
We say that $\calT$ \emph{hardcodes} producible assembly $\alpha$ if
1) every glue in $\alpha$ is unique,
2) every tile type in $T$ appears in $\alpha$,
3) there are no glue mismatches in $\alpha$, and
4) all glues on unbound sides in $\alpha$ are null.



\begin{lem}\label{lem-temp1-hier-unique-char}
  Let $\calT=(T,1)$ be a temperature 1 hierarchical TAS.
  Then $\calT$ uniquely produces $\alpha \in \prodasm{\calT}$ if and only if $\calT$ hardcodes $\alpha$. %every glue in $\alpha$ is unique, every tile type in $T$ appears in $\alpha$, there are no glue mismatches in $\alpha$, and all glues on unbound sides in $\alpha$ are null.
\end{lem}

\begin{proof}
  The implication ``$\calT$ hardcodes $\alpha$'' $\implies$ ``$\calT$ uniquely produces $\alpha$'' is clear.

  To see that the converse holds, suppose $\calT$ uniquely produces $\alpha$.
  Recall our observation that at any temperature, $\calT$ uniquely produces $\alpha$ if and only if for every producible assembly $\beta$, there is a translation $\beta'$ of $\beta$ such that $\beta' \sqsubseteq \alpha$.
  If $\alpha$ does not contain some tile type $t \in T$, then since $t$ is a producible assembly, no translation of $t$ is a subassembly of $\alpha$, so $\alpha$ is not uniquely produced, a contradiction.
  If $\alpha$ contains a non-null glue on an unbound side, then $\alpha$ is not terminal, a contradiction.
  It remains to show that every glue in $\alpha$ is unique and there are no glue mismatches in $\alpha$.

  At temperature 1, the set of producible assemblies is precisely the set of stable assemblies, because all producible assemblies must be stable by definition, and all stable assemblies are producible by single-tile attachment starting from an arbitrary tile in the assembly.




  To see that the converse holds, suppose there are no glue mismatches, all glues on unbound sides in $\alpha$ are null, but a glue is duplicated between two pairs of adjacent tiles $(t_1,t_2)$ and $(t_3,t_4)$. %, assuming without loss of generality that $t_1$ lies to the left of $t_2$ and $t_3$ lies to the right of $t_4$ in $\alpha$.
  We will show this implies $\alpha$ is not uniquely produced by $\calT$.
  Suppose that $t_1$ and $t_3$ are not the same tile type.
  Let $\alpha - t_1 + t_3$ denote $\alpha$ with $t_1$ replaced by $t_3$.
  If $\alpha - t_1 + t_3$ is stable, hence producible, then since $\dom \alpha = \dom (\alpha - t_1 + t_3)$ but $\alpha \neq \alpha - t_1 + t_3$, $\alpha$ is not uniquely produced.
  If $\alpha - t_1 + t_3$ is stable, then $t_1$ was a cut vertex of the binding graph of $\alpha$.
  Let $\beta$ be the connected component of $\alpha - t_1$ containing $t_2$.
  Then $\beta - t_1 + t_3$ is stable.
\end{proof}

%We employ the following easily-verified observation: if an assembly $\alpha$ is producible in the hierarchical model at temperature 1, and if $\alpha' \sqsubset \alpha$ is a connected assembly obtained by removing a single tile from $\alpha$, then $\alpha'$ is producible as well.

\begin{thm}
  There is an algorithm that solves the $\hUPV$ problem in time $O(|\alpha| + |\calT|)$.
\end{thm}

\begin{proof}
    $\alpha$ is producible at temperature 1 in the hierarchical aTAM if and only if its binding graph is connected, and it is terminal if and only if its unbound sides have the null glue (since if any producible assembly could attach to $\alpha$, then a single tile could attach as well, because this is temperature 1).
    These conditions can be checked in time $O(|\alpha|)$.

    We claim that $\alpha$ is the unique producible terminal assembly of $\calT$ if and only if
    1) $\alpha$ has no mismatches, checkable in time $O(|\alpha|)$,
    2) for all directions $d \in \{\dN,\dS,\dE,\dW\}$ and all tile types $t_1 \neq t_2$, $t_1(d) \neq t_2(d)$ (no two distinct tile types share a glue on the same side), checkable in time $O(|\calT|)$, and
    3) $\alpha$ contains every tile type in $T$, checkable in time $O(|\alpha| + |\calT|)$.


    To see that this claim is true, suppose condition (1) fails.
    Then one of the mismatching tiles can be removed and the resulting assembly is still producible, and a different tile type could go in its place, showing a producible assembly $\beta \neq \alpha$ with $\dom \alpha = \dom \beta$, whence $\alpha$ is not uniquely produced.
    Suppose condition (2) fails.
    Then whenever tile type $t_1$ appears in $\alpha$, it could be replaced with $t_2$, implying a producible assembly $\beta \neq \alpha$ with $\dom \alpha = \dom \beta$, whence $\alpha$ is not uniquely produced.
    Suppose condition (3) fails, so there is a tile type $t\in T$ not appearing in $\alpha$.
    Then since $\alpha$ is terminal, either $\calT$ can produce an infinite assembly (hence it does not uniquely produce $\alpha$) or there is some terminal assembly $\beta$ containing $t$, and $\beta \neq \alpha$ since $\alpha$ does not contain $t$, so $\alpha$ is not uniquely produced.
    Therefore if $\calT$ is directed, conditions (1), (2), and (3) hold.

    Conversely, suppose $\calT$ is not directed and condition (3) holds.
    It suffices to show that one of conditions (1), (2), or (3) fails.
    Since $\calT$ is not directed, there is a producible assembly $\beta$ such that no translation of $\beta$ is a subassembly of $\alpha$.
    Since $\alpha$ contains every tile type (condition (3)), assume $\beta$ is translated so that one of its tile types $t$ is positioned at the same position as the same tile type in $\alpha$.
    There are two cases: a) $\beta(p) = \alpha(p)$ for every $p \in \dom \beta \cap \dom \alpha$, and b) $\beta(p) \neq \alpha(p)$ for some $p \in \dom \beta \cap \dom \alpha$.
    In case (a), since $\beta \not \sqsubseteq \alpha$, then $\dom \beta \setminus \dom \alpha \neq \emptyset$, so there is some positive-strength glue on an unbound side of $\alpha$ (on a tile in some position $p \in \dom \alpha \cap \dom \beta$), contradicting our observation above that $\alpha$ is terminal.
    In case (b), there is some adjacent positions $p_1,p_2 \in \dom \alpha \cap \dom \beta$, binding with positive strength in $\beta$, such that $\alpha(p_1) = \beta(p_1)$ but $\alpha(p_2) \neq \beta(p_2)$.
    This implies that either $\alpha(p_1)$ mismatches $\alpha(p_2)$ (condition (1) fails), or that condition (2) fails, since this would imply that two different tile types $t_1 = \beta(p_2)$ and $t_2 = \alpha(p_2)$ share the same glue in direction $p_1 - p_2$.
\end{proof}

\end{comment}

main.bbl
\begin{thebibliography}{10}

\bibitem{RNaseSODA2010}
Zachary Abel, Nadia Benbernou, Mirela Damian, Erik~D. Demaine, Martin~L.
  Demaine, Robin Flatland, Scott Kominers, and Robert Schweller.
\newblock Shape replication through self-assembly and {RN}ase enzymes.
\newblock In {\em SODA 2010: Proceedings of the Twenty-first Annual ACM-SIAM
  Symposium on Discrete Algorithms}, Austin, Texas, 2010. Society for
  Industrial and Applied Mathematics.

\bibitem{ACGHKMR02}
Leonard~M. Adleman, Qi~Cheng, Ashish Goel, Ming-Deh~A. Huang, David Kempe,
  Pablo~Moisset de~Espan\'{e}s, and Paul W.~K. Rothemund.
\newblock Combinatorial optimization problems in self-assembly.
\newblock In {\em STOC 2002: Proceedings of the Thirty-Fourth Annual ACM
  Symposium on Theory of Computing}, pages 23--32, 2002.

\bibitem{AGKS05}
Gagan Aggarwal, Qi~Cheng, Michael~H. Goldwasser, Ming-Yang Kao, Pablo~Moisset
  de~Espan\'{e}s, and Robert~T. Schweller.
\newblock Complexities for generalized models of self-assembly.
\newblock {\em SIAM Journal on Computing}, 34:1493--1515, 2005.
\newblock Preliminary version appeared in SODA 2004.

\bibitem{BarSchRotWin09}
Robert~D. Barish, Rebecca Schulman, Paul W.~K. Rothemund, and Erik Winfree.
\newblock An information-bearing seed for nucleating algorithmic self-assembly.
\newblock {\em Proceedings of the National Academy of Sciences},
  106(15):6054--6059, March 2009.

\bibitem{TwoHandsBetterThanOne}
Sarah Cannon, Erik~D. Demaine, Martin~L. Demaine, Sarah Eisenstat, Matthew~J.
  Patitz, Robert~T. Schweller, Scott~M. Summers, and Andrew Winslow.
\newblock Two hands are better than one (up to constant factors).
\newblock In {\em STACS 2013: Proceedings of the Thirtieth International
  Symposium on Theoretical Aspects of Computer Science}, pages 172--184, 2013.

\bibitem{CheDot12}
Ho-Lin Chen and David Doty.
\newblock Parallelism and time in hierarchical self-assembly.
\newblock In {\em SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium
  on Discrete Algorithms}, pages 1163--1182. SIAM, 2012.

\bibitem{CLRS01}
Thomas~H. Cormen, Charles~E. Leiserson, Ronald~L. Rivest, and Clifford Stein.
\newblock {\em Introduction to Algorithms}.
\newblock MIT Press, 2001.

\bibitem{DDFIRSS07}
Erik~D. Demaine, Martin~L. Demaine, S{\'a}ndor~P. Fekete, Mashhood Ishaque,
  Eynat Rafalin, Robert~T. Schweller, and Diane~L. Souvaine.
\newblock Staged self-assembly: Nanomanufacture of arbitrary shapes with
  ${O}(1)$ glues.
\newblock {\em Natural Computing}, 7(3):347--370, 2008.
\newblock Preliminary version appeared in {D}{N}{A} 2007.

\bibitem{DemEisIshWinOneDimStagedjournal}
Erik~D. Demaine, Sarah Eisenstat, Mashhood Ishaque, and Andrew Winslow.
\newblock One-dimensional staged self-assembly.
\newblock {\em Natural Computing}.
\newblock To appear. Preliminary version appeared in {DNA} 2011.

\bibitem{TwoHandedNotIntrinsicallyUniversalconf}
Erik~D. Demaine, Matthew~J. Patitz, Trent Rogers, Robert~T. Schweller, Scott~M.
  Summers, and Damien Woods.
\newblock The two-handed tile assembly model is not intrinsically universal.
\newblock In {\em ICALP 2013: Proceedings of the 40th International Colloquium
  on Automata, Languages and Programming}, July 2013.

\bibitem{DemPatSchSum2010RNase}
Erik~D. Demaine, Matthew~J. Patitz, Robert~T. Schweller, and Scott~M. Summers.
\newblock Self-assembly of arbitrary shapes using {RN}ase enzymes: Meeting the
  {K}olmogorov bound with small scale factor.
\newblock In {\em STACS 2011: Proceedings of the 28th International Symposium
  on Theoretical Aspects of Computer Science}, 2011.

\bibitem{DotCACM}
David Doty.
\newblock Theory of algorithmic self-assembly.
\newblock {\em Communications of the ACM}, 55(12):78--88, December 2012.

\bibitem{TAMIU}
David Doty, Jack~H. Lutz, Matthew~J. Patitz, Robert~T. Schweller, Scott~M.
  Summers, and Damien Woods.
\newblock The tile assembly model is intrinsically universal.
\newblock In {\em FOCS 2012: Proceedings of the 53rd Annual IEEE Symposium on
  Foundations of Computer Science}, pages 302--310. IEEE, 2012.

\bibitem{DotPatReiSchSum10}
David Doty, Matthew~J. Patitz, Dustin Reishus, Robert~T. Schweller, and
  Scott~M. Summers.
\newblock Strong fault-tolerance for self-assembly with fuzzy temperature.
\newblock In {\em FOCS 2010: Proceedings of the 51st Annual IEEE Symposium on
  Foundations of Computer Science}, pages 417--426. IEEE, 2010.

\bibitem{GotEtAl00}
Kei Goto, Yoko Hinob, Takayuki Kawashima, Masahiro Kaminagab, Emiko Yanob, Gaku
  Yamamotob, Nozomi Takagic, and Shigeru Nagasec.
\newblock Synthesis and crystal structure of a stable {S}-nitrosothiol bearing
  a novel steric protection group and of the corresponding {S}-nitrothiol.
\newblock {\em Tetrahedron Letters}, 41(44):8479--8483, 2000.

\bibitem{HellerPugh1}
Wilfried Heller and Thomas~L. Pugh.
\newblock ``{S}teric protection'' of hydrophobic colloidal particles by
  adsorption of flexible macromolecules.
\newblock {\em Journal of Chemical Physics}, 22(10):1778, 1954.

\bibitem{HellerPugh2}
Wilfried Heller and Thomas~L. Pugh.
\newblock ``{S}teric'' stabilization of colloidal solutions by adsorption of
  flexible macromolecules.
\newblock {\em Journal of Polymer Science}, 47(149):203--217, 1960.

\bibitem{HopcroftTarjanBiconnected73}
John Hopcroft and Robert Tarjan.
\newblock Algorithm 447: efficient algorithms for graph manipulation.
\newblock {\em Communications of the ACM}, 16(6):372--378, June 1973.

\bibitem{jSSADST}
James~I. Lathrop, Jack~H. Lutz, and Scott~M. Summers.
\newblock Strict self-assembly of discrete {S}ierpinski triangles.
\newblock {\em Theoretical Computer Science}, 410:384--405, 2009.
\newblock Preliminary version appeared in CiE 2007.

\bibitem{Luhrs10}
Chris Luhrs.
\newblock Polyomino-safe {DNA} self-assembly via block replacement.
\newblock {\em Natural Computing}, 9(1):97--109, March 2010.
\newblock Preliminary version appeared in {DNA} 2008.

\bibitem{PatitzSurvey12}
Matthew~J. Patitz.
\newblock An introduction to tile-based self-assembly.
\newblock In {\em UCNC 2012: Proceedings of the 11th international conference
  on Unconventional Computation and Natural Computation}, pages 34--62, Berlin,
  Heidelberg, 2012. Springer-Verlag.

\bibitem{PatSumIdentifyingJournal}
Matthew~J. Patitz and Scott~M. Summers.
\newblock Identifying shapes using self-assembly.
\newblock {\em Algorithmica}, 64(3):481--510, 2012.
\newblock Preliminary version appeared in ISAAC 2010.

\bibitem{Roth01}
Paul W.~K. Rothemund.
\newblock {\em Theory and Experiments in Algorithmic Self-Assembly}.
\newblock PhD thesis, University of Southern California, December 2001.

\bibitem{RotWin00}
Paul W.~K. Rothemund and Erik Winfree.
\newblock The program-size complexity of self-assembled squares (extended
  abstract).
\newblock In {\em STOC 2000: Proceedings of the Thirty-Second Annual ACM
  Symposium on Theory of Computing}, pages 459--468, 2000.

\bibitem{SchWin07}
Rebecca Schulman and Erik Winfree.
\newblock Synthesis of crystals with a programmable kinetic barrier to
  nucleation.
\newblock {\em Proceedings of the National Academy of Sciences},
  104(39):15236--15241, 2007.

\bibitem{SchWin09}
Rebecca Schulman and Erik Winfree.
\newblock Programmable control of nucleation for algorithmic self-assembly.
\newblock {\em SIAM Journal on Computing}, 39(4):1581--1616, 2009.
\newblock Preliminary version appeared in DNA 2004.

\bibitem{SchSheSODAFuel}
Robert~T. Schweller and Michael Sherman.
\newblock Fuel efficient computation in passive self-assembly.
\newblock In {\em SODA 2013: Proceedings of the 24th Annual ACM-SIAM Symposium
  on Discrete Algorithms}, pages 1513--1525, January 2013.

\bibitem{WadeOrganicChemistry91}
Leroy~G. Wade.
\newblock {\em Organic {C}hemistry}.
\newblock Prentice Hall, 2nd edition, 1991.

\bibitem{Winf98}
Erik Winfree.
\newblock {\em Algorithmic Self-Assembly of {D}{N}{A}}.
\newblock PhD thesis, California Institute of Technology, June 1998.

\bibitem{Winfree98simulationsof}
Erik Winfree.
\newblock Simulations of computing by self-assembly.
\newblock Technical Report CaltechCSTR:1998.22, California Institute of
  Technology, 1998.

\bibitem{Winfree06}
Erik Winfree.
\newblock Self-healing tile sets.
\newblock In Junghuei Chen, Natasa Jonoska, and Grzegorz Rozenberg, editors,
  {\em Nanotechnology: Science and Computation}, Natural Computing Series,
  pages 55--78. Springer, 2006.

\bibitem{WinLiuWenSee98}
Erik Winfree, Furong Liu, Lisa~A. Wenzler, and Nadrian~C. Seeman.
\newblock Design and self-assembly of two-dimensional {D}{N}{A} crystals.
\newblock {\em Nature}, 394(6693):539--44, 1998.

\end{thebibliography}
