Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles (extended abstract)
Jacob Hendricks \thanks{Department of Computer Science and Computer Engineering
University of Arkansas
Fayetteville
AR
USA. \protect\url{jhendric@uark.edu
In this paper, we investigate the abilities of systems of self-assembling tiles which can each pass a constant number of signals to their immediate neighbors to create replicas of input shapes. Namely, we work within the Signal-passing Tile Assembly Model (STAM), and we provide a universal STAM tile set which is capable of creating unbounded numbers of assemblies of shapes identical to those of input assemblies. The shapes of the input assemblies can be arbitrary 2-dimensional hole-free shapes at scale factor 2. This greatly improves previous shape replication results in self-assembly that required models in which multiple assembly stages and/or bins were required, and the shapes which could be replicated were quite constrained. % % %
biomimicry-with-stam.tex
\newif\iflncs
%
\lncstrue
\iflncs
\documentclass{llncs}
\else
\documentclass{article}[11]
\usepackage{fullpage}
\fi

\usepackage{appendix}
\usepackage{amsmath}
\usepackage{amssymb}
\iflncs
\else
\usepackage{amsthm}
\fi
\usepackage{ifpdf}
\usepackage{algorithmic}
%
\usepackage{subfig}
\usepackage{wrapfig}
%
\usepackage{cite}
\usepackage{colortbl}
\usepackage{tikz}
\usepackage{morefloats}
\usepackage{enumitem}

%
%
%
%
%
%
%
%
%
%

\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}

\usepackage{commands-tam}

\ifpdf

  %
  %
  \usepackage[pdftex]{epsfig}
  %
  \usepackage[pdftex]{hyperref}

\else

    %
    %
    \usepackage[dvips]{epsfig}
    %
    \newcommand{\href}[2]{#2}

\fi

\newif\ifabstract
\newif\iffull

%
%

%
\abstracttrue


\ifabstract
	\fullfalse
\else
	\fulltrue
\fi


\newtoks\magicAppendix
\magicAppendix={}
\newtoks\magictoks
\newif\iflater
\laterfalse
\ifabstract
\long\def\later#1{\magictoks={#1}%
  \edef\magictodo{\noexpand\magicAppendix={\the\magicAppendix \par
    \the\magictoks%
  }}
  \magictodo}
\long\def\both#1{\magictoks={#1}%
  \edef\magictodo{\noexpand\magicAppendix={\the\magicAppendix \par
    \noexpand\setcounter{theorem-preserve}{\noexpand\arabic{theorem}}%
    \noexpand\setcounter{theorem}{\arabic{theorem}}%
    \noexpand\setcounter{section-preserve}{\noexpand\arabic{section}}%
    \noexpand\setcounter{section}{\arabic{section}}%
	\noexpand\let\noexpand\oldsection=\noexpand\thesection
	\noexpand\def\noexpand\thesection{\thesection}
	\noexpand\let\noexpand\oldlabel=\noexpand\label
	\noexpand\let\noexpand\label=\noexpand\blank
    %
    \the\magictoks%
    \noexpand\setcounter{theorem}{\noexpand\arabic{theorem-preserve}}%
    \noexpand\setcounter{section}{\noexpand\arabic{section-preserve}}%
	\noexpand\let\noexpand\thesection=\noexpand\oldsection
	\noexpand\let\noexpand\label=\noexpand\oldlabel
  }}
  \magictodo
  \the\magictoks}
\else
\long\def\later#1{#1}
\long\def\both#1{#1}
\fi
\long\def\magicappendix{
	\latertrue%
	\the\magicAppendix%
}

\iflncs
\newtheorem{observation}[theorem]{Observation}
\else
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\fi
%

\newcommand{\rank}{{\rm rank}}
\newcommand{\ball}{{\rm Ball}}
\newcommand{\grid}{{\rm grid}}

%
%
%
%
%

\title{Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles (extended abstract)}

\author{
    Jacob Hendricks
        \thanks{Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR, USA.
        \protect\url{jhendric@uark.edu}.
        This author's research was supported in part by National Science Foundation grant CCF-1422152.}
\and
	Matthew J. Patitz
        \thanks{Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR, USA.
        \protect\url{mpatitz@self-assembly.net}.
        This author's research was supported in part by National Science Foundation grant CCF-1422152.}
\and
    Trent A. Rogers
        \thanks{Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR, USA.
        \protect\url{tar003@uark.edu}.
        This author's research was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1450079, and National Science Foundation grant CCF-1422152.}
}
\institute{}
\date{}


\begin{document}

\maketitle

\begin{abstract}
In this paper, we investigate the abilities of systems of self-assembling tiles which can each pass a constant number of signals to their immediate neighbors to create replicas of input shapes.  Namely, we work within the Signal-passing Tile Assembly Model (STAM), and we provide a universal STAM tile set which is capable of creating unbounded numbers of assemblies of shapes identical to those of input assemblies.  The shapes of the input assemblies can be arbitrary 2-dimensional hole-free shapes at scale factor 2.  This greatly improves previous shape replication results in self-assembly that required models in which multiple assembly stages and/or bins were required, and the shapes which could be replicated were quite constrained.
%

%

%
\end{abstract}

%

\input{intro}
\input{prelims}
\input{frame-building}
\input{replication2}
%
\vspace{-25pt}
\bibliographystyle{amsplain}
\bibliography{tam}

\ifabstract
\newpage
%
\appendix
\magicappendix
\fi

\end{document}

frame-building.tex
\newcommand{\cgSE}{CG_{SE}}
\newcommand{\cgSEi}[1]{CG_{SE_{#1}}}

\newcommand{\cgNE}{CG_{NE}}
\newcommand{\cgNW}{CG_{NW}}
\newcommand{\cgSW}{CG_{SW}}

\newcommand{\cgN}{CG_N}
\newcommand{\cgW}{CG_W}
\newcommand{\cgS}{CG_S}

\newcommand{\necav}{conc_{NE}}
\newcommand{\secav}{conc_{SE}}
\newcommand{\swcav}{conc_{SW}}
\newcommand{\nwcav}{conc_{NW}}

\newcommand{\necon}{conv_{NE}}
\newcommand{\secon}{conv_{SE}}
\newcommand{\swcon}{conv_{SW}}
\newcommand{\nwcon}{conv_{NW}}

\newcommand{\frametwo}[2][2]{frame{#1}_{#2}}

\newcommand{\on}{\mathtt{on}}
\newcommand{\off}{\mathtt{off}}
\newcommand{\latent}{\mathtt{latent}}

\newcommand{\frametiles}{T_{frame}}
\newcommand{\layerone}{T_{layer1}}
\newcommand{\layertwo}{T_{layer2}}
\newcommand{\cdtiles}{T_{CD}}
\newcommand{\alphatiles}{T_{\alpha}}


\section{Frame Building}\label{sec:frame-building}

Throughout this paper, we provide constructions which take as input assemblies of arbitrary 2D hole-free shapes.  For the frame building construction described in this section, no scale factor is necessary.  For the replication construction of Section~\ref{sec:rep}, the shapes require a scale factor of 2. All input assemblies have completely uniform perimeters in terms of glue labels, meaning that no location on a perimeter is marked any differently from the others.  Given the local nature of the self-assembly process, namely that tiles bind based only on local interactions of matching glues, and also with the order and locations of tile attachments being nondeterministic and growth of assemblies massively in parallel, a distributed problem such as ``leader election'' can be quite difficult, and similarly so is the problem of uniquely identifying exactly one point on the perimeter of an input assembly when no assumptions can be made about the shape other than the facts that it (1) is connected and (2) has no interior holes which are completely surrounded by the assembly.  Therefore, in this section we provide a construction which is a single universal STAM system capable of forming \emph{frames}, or simply borders composed of tiles, completely surrounding input assemblies in such a way that the growth of the frames performs a distributed algorithm which uniquely identifies exactly one perimeter location on each input shape.  While this algorithm and STAM system, as well as several of the novel techniques, are of independent interest, they also play integral roles in the remaining constructions of this paper and will potentially also provide a useful toolkit for future constructions in others.

At a very high-level, the frame building construction can be broken into three main components.  First, a series of layers of tiles attach to the input assembly $\alpha$, each slowly helping to fill in the openings to any concavities, until eventually $\alpha$ is enclosed in an assembly which has a rectangular outer layer.  Second, that rectangular layer is able to detach after its unique southeast corner tile ``gadget'' initiates the propagation of a signal inward through all of the layers to the easternmost of the southernmost tiles which have attached directly to $\alpha$.  The tile that is immediately to the left of this tile is elected the ``leader'' of the frame.  Third, the leader initiates a signal which propagates in a counterclockwise direction around $\alpha$, carefully ensuring that the entire perimeter of $\alpha$ is surrounded by tiles which have bound to it and made a complete ``mold'' of the shape.  After this is accomplished, the entire frame detaches from $\alpha$.  The result is a perfect mold of $\alpha$, with generic glues exposed around its entire interior surface except for one specific location, the leader, which exposes a unique glue.  It is from this unique glue that the frame assembly will then be able to initiate the growth which fills it in and makes a replica of $\alpha$.


%
\input{new-frame}
%

%

%

\input{marking-a-tile}

\input{frame-proof}


frame-conventions.tex
%

Throughout this paper, we will use the following definitions and conventions:

We define a \emph{shape} as a finite, connected subset of $\Z^2$.  Following~\cite{ShapeIdentAlgo}, we say that a shape $s$ is \emph{hole-free} if the complement of $s$ is an infinite connected subset of $\Z^2$. We say that an assembly $\alpha$ is hole-free if $\dom(\alpha)$ is hole-free.  Then, an \emph{input assembly} is a non-empty, $\tau$-stable, hole-free assembly $\alpha$ such that every glue on the perimeter of $\alpha$ is strength 1 and of the same type. Throughout this section, we denote an input assembly by $\alpha$ and the type of the glue exposed on the perimeter of $\alpha$ by $x$.  Furthermore, a \emph{side} of a shape is any segment of the perimeter which connects two vertices (each of which can be convex or concave).

\ifabstract
\later{
\subsection{Additional definitions}

The algorithm that we present here will make use of many different gadgets and refer to various features of an input assembly and the shape of this input assembly. For convenience and brevity, we use the following conventions.

\begin{enumerate}

    \item[-] When a tile initially binds to an assembly, we call the sides which have glues that participate in that initial binding event the \emph{input} side(s), and the other sides the \emph{output} side.
    \item[-] Respectively for each of northeast, southeast, southwest, and northwest, define convex corners with that pair of incident edges as $\necon$, $\secon$, $\swcon$, and $\nwcon$
    \item[-] Respectively for each of northeast, southeast, southwest, and northwest, define concave corners with that pair of incident edges as $\necav$, $\secav$, $\swcav$, and $\nwcav$
    \item[-] CCW: counterclockwise, CW: clockwise
    \item[-] Let $R$ be the smallest bounding rectangle for $\alpha$ (i.e. the smallest rectangle that completely contains $\alpha$)
    \item[-] Let $PERIM(\alpha)$ be the set of all perimeter edges of $\alpha$.

	\item[-] Let $C$ be the convex hull of the set, $S$ say, of points in $\R^2$ defined by the corners of each tile. (That is, $(x,y)\in S$ iff $(x - \frac{1}{2},y - \frac{1}{2})$, $(x + \frac{1}{2},y - \frac{1}{2})$, $(x - \frac{1}{2},y + \frac{1}{2})$, or $(x + \frac{1}{2},y + \frac{1}{2})$ is in $\dom(\alpha)$.)
 	\item[-] We define $EXT(\alpha)$ to be the set of edges in $PERIM(\alpha)$ that are completely contained in the boundary of $C$.
 	\item[-] We define $INT(\alpha)$ to be $PERIM(\alpha) / EXT(\alpha)$.
	\item[-] Then, an \emph{concavity} of $\alpha$ is defined to be a subset, $E$, of edges of $INT(\alpha)$ such that each edge of $E$ is incident to some other edge in $E$.
\end{enumerate}
For an intuitive picture of the last four definitions above, see Figure~\ref{fig:convex-hull}.

\begin{figure}[htp]
\centering
    \includegraphics[width=3in]{images/convex-hull}
    \caption{An input assembly $\alpha$ consisting of the gray tiles. (Temperature-1 $x$ glues on the exterior of $\alpha$ are not shown.) The dashed line depicts the boundary of the convex hull $C$. The edges highlighted in blue make up the edges of $EXT(\alpha)$, and the edges highlighted in red make up the edges of $INT(\alpha)$. }
  \label{fig:convex-hull}
\end{figure}

} %

frame-proof.tex







\subsection{Correctness of the frame construction}\label{sec:frame-proof}

The goal of the frame construction is to result in an assembly which completely encases $\alpha$, making a perfect mold of its shape, and then detaches.  Furthermore, and extremely importantly, that mold must have uniquely identified exactly one tile on its interior (i.e. its ``elected leader'').  We now state the properties which are guaranteed by the frame construction.  Their proofs can be found in Section~\ref{sec:frame-proof-app} of the appendix.

First, for notation we will refer to the collision detections tiles as $\cdtiles \subset T$, the tile type(s) which make up $\alpha$ as $\alphatiles$, and the remaining tiles as $\frametiles = (T - \cdtiles) - \alphatiles$.

\begin{lemma}\label{lem:rectangle-layer}
For each STAM system $\calT = (T,\alpha,2)$ with tile set $T$ (i.e. the frame building tile set) and input assembly $\alpha$, there exists some constant $c_{\alpha}$ such that regardless of the assembly sequence, after $c$ tile attachments a rectangular frame layer of tiles in $\frametiles$ will have grown around $\alpha$.
\end{lemma}

\begin{lemma}\label{lem:rectangle-detach}
For each STAM system $\calT = (T,\alpha,2)$ with tile set $T$ (i.e. the frame building tile set) and input assembly $\alpha$, as a frame assembly grows, no subassembly containing tiles of $\frametiles$ can completely detach from the assembly unless it consists of a path which forms a complete and exact rectangle.  Furthermore, the first such rectangular path will detach and then no further layers will grow.
\end{lemma}

\begin{lemma}\label{lem:marking}
For each STAM system $\calT = (T,\alpha,2)$ with tile set $T$ (i.e. the frame building tile set) and input assembly $\alpha$, as a frame assembly grows, the eventual detachment of the rectangular layer will result in a single tile of the frame (the leader), which is adjacent to a location of $\alpha$, activating a $z$ glue.
\end{lemma}

\begin{lemma}\label{lem:full-mold}
The leader tile will initiate a message which will propagate around $\alpha$ and guarantee that for every location directly or diagonally adjacent to a tile in $\alpha$, layer 1 contains a tile in this location. Moreover, after all pending signals of the $br$ message have fired, the entire frame assembly detaches from $\alpha$ exposing on its interior a unique glue activated on only the leader.
\end{lemma}

\begin{lemma}\label{lem:no-combine}
Let $\beta$ and $\gamma$ be distinct producible assemblies of $\mathcal{T}$ that each have an input assembly as a subassembly. Then $\beta$ and $\gamma$ cannot bind.
\end{lemma}

\ifabstract
\later{

\subsection{Details of correctness of the frame construction}\label{sec:frame-proof-app}

First, for notation we will refer to the collision detections tiles as $\cdtiles \subset T$, the tile type(s) which make up $\alpha$ as $\alphatiles$, and the remaining tiles as $\frametiles = T - \cdtiles - \alphatiles$.

\begin{lemma}\label{lem:rectangle-layer}
For each STAM system $\calT = (T,\alpha,2)$ with tile set $T$ (i.e. the frame building tile set) and input assembly $\alpha$, there exists some constant $c_{\alpha}$ such that regardless of the assembly sequence, after $c$ tile attachments a rectangular frame layer of tiles in $\frametiles$ will have grown around $\alpha$.
\end{lemma}


\begin{proof}

To prove Lemma~\ref{lem:rectangle-layer}, the main point we must prove is that, regardless of the shape of $\alpha$, every possible assembly sequence of $\calT$ will, in a finite number of steps, build a rectangular layer.  To prove this, we begin by noting that a rectangle is the only shape with no concavities.  The frame, which is the portion of the assembly consisting of tiles of $\frametiles$, grows as a series of (sometimes partial) layers around (portions of) $\alpha$.  Every tile of $\frametiles$ attaches (either as a singleton, preformed duple, or 3-tile $\cgSE$) to $\alpha$, a tile of a layer which is between it and $\alpha$ (i.e. part of a layer that grew before and between), or a doubling row.  This follows directly from the definitions of the tile types of $\frametiles$ and the fact that the only glues that are $\on$ before they attach to the assembly require at least one attachment to $\alpha$, a previous layer of the frame, or a doubling row to allow a stable attachment.  Every portion of a layer which cannot grow from the north output of a $\cgSE$ to the west input a $\cgSE$ (the same or a different $\cgSE$) must be prevented from doing so by (1) a collision with either $\alpha$ or a tile of a previous layer or doubling row, or (2) a situation where it grew over both tiles of the south side of a $\cgSE$.

Case 1:  In any such case of a collision, there must be a location adjacent to that path where a collision detection tile or duple can attach due to the fact that such a path will expose $c$ glues along its entire right side, and any collision ensures that there is a tile (of $\alpha$, some portion of layer 1, some portion of a layer 2 path, or a doubling row) next to that path which exposes a glue matching one on a collision detection tile/duple.  The design of the collision detection tiles, as seen in Figures~\ref{fig:collision-detection-tiles} and \ref{fig:collision-detection-corner-cases}, ensures that regardless of the relative locations of those two glues, there is a collision detection tile/duple which can attach.  This attachment will begin the propagation of a $q$ message which will propagate back to the $\cgSE$ which initiated the growth of that layer.  (Various collision detection scenarios can be scene in Figures~\ref{fig:new-frame2-concave-collision1},\ref{fig:new-frame2-duple-detect-collision},\ref{fig:new-frame2-single-detect-collision},
\ref{fig:standard-row-nonquitting-cgse},\ref{fig:special-collision-detection}.)

This $q$ message must be able to follow the path exactly backwards by the definitions of the layer 2 tiles, eventually arriving at the $\cgSE$ from which it grew.  This will cause that $\cgSE$ to activate glues which allow another $\cgSE$ to attach to its outside, initiating the growth of another layer, and it will also continue to pass the $q$ message CW which will initiate growth of a doubling row on the south side of a layer 2 path which either may have already collided, or later will, with the west side of that $\cgSE$.  Note that the $\cgSE$ receiving the $q$ message could be prevented from allowing the attachment of a new $\cgSE$ on its outside by a row (or doubling row) which has grown underneath it.  This is discussed in case 2 next, but note that in this case a new layer is also initiated. %

\begin{figure}
    \centering
    \includegraphics[width=2.0in]{images/collision-detection-corner-cases2}
    \caption{Example frame growth around an input assembly $\alpha$ (grey) which is nearly rectangular (with the exception of a single-tile concavity on the southeast corner). $\cgSE$'s are green, standard paths in light blue, and doubling rows in dark blue. This example shows how, when a path grows across the bottom of a $\cgSE$, it initiates the growth of a vertical doubling row, and the attachment of another $\cgSE$ at an offset of $(2,-2)$ from the first.}
    \label{fig:collision-detection-corner-cases2}
\end{figure}

Case 2:  When a row grows across the south side of a $\cgSE$, it detects that situation and initiates a vertical doubling row which grows up the east side of the row initiated by that $\cgSE$.  Additionally, the bottom tile of that vertical doubling row exposes the glues necessary to allow a $\cgSE$ to bind to it, thus initiating the growth of a new layer. (An example can be seen in Figure~\ref{fig:collision-detection-corner-cases2}.)

At this point, we distinguish the cases of $\cgSE$'s which attach to corners on $EXT(\alpha)$ (i.e. on the exterior of $\alpha$, not in a concavity) with those which attach to corners on $INT(\alpha)$.  We call the former \emph{exterior} $\cgSE$'s and the latter \emph{interior} $\cgSE$'s.  It is clearly possible for an interior $\cgSE$ to attach in a concavity which is too narrow for a new $\cgSE$ to attach to its outside, but our argument does not depend on the ability of such $\cgSE$'s to initiate growth of new layers so we will ignore them.  (This is because growth inside, and into, concavities must eventually completely fill at least the entrances to those concavities - even if some portions of concavities remain unfilled.  As long as exterior $\cgSE$'s can continue to initiate the growth of new layers until a rectangular layer is formed, the layers will eventually grow over the filled in entrances to all concavities.) Instead we will focus on external $\cgSE$'s (implicitly) for the rest of the proof, and we will note that because of the handling of Case 1 and Case 2 above, a \emph{stack} of exterior $\cgSE$'s (i.e. a sequence of $\cgSE$'s which have bound either directly to each other or the doubling rows separating them, growing outward from the same corner.  See Figure~\ref{fig:stack-catch-up} for an example) can always continue outward growth of additional layers except for in the case where one stack, $s_1$, which is to the west of a second stack, $s_2$, grows to a point where the $x$-coordinate of the eastern tiles of a $\cgSE$ in $s_1$ is greater than the $x$-coordinates of all portions of $\cgSE$'s in $s_2$.  When this occurs, we say that $s_2$ is \emph{covered}, and at this point new layers are no longer initiated by $s_2$ (although the final $\cgSE$ of $s_2$ must receive a $q$ message since its layer is not a rectangle, and therefore the tiles of the path which grew from it will expose $x2$ glues allowing a path initiated by a $\cgSE$ of $s_1$ to grow around its outside edge since one path from that stack will collide with the southeast tile of $s_2$'s final $\cgSE$, allowing a collision detection duple to attach and pass a $q$ message backward, finally allowing a path from $s_1$ to envelope $s_2$), but will continue to be initiated by $s_1$ (assuming none is yet rectangular).  We will now discuss why this is not only desired, but guaranteed to happen so that eventually there is exactly one stack of $\cgSE$'s, which must be the case for a rectangular layer to exist.

\begin{figure}
    \centering
    \includegraphics[width=4.0in]{images/stack-catch-up}
    \caption{Example frame growth around an input assembly $\alpha$ (grey) which is nearly rectangular (with the exception of a single-tile concavity on the south). (Left) The first few layers of growth from two stacks of exterior $\cgSE$'s.  $\cgSE$'s are green, standard paths in light blue, and doubling rows in dark blue. These first few layers demonstrate how, in the growth of the stack on the left, there is a race condition between the growth of paths underneath the $\cgSE$'s, which would initiate growth of a vertical doubling row before the next $\cgSE$ attaches (as occurs beneath the first of the $\cgSE$'s), and the direct attachment of one $\cgSE$ below another due to the backwards propagation of the $q$ signal initiated when the upward growing row from a $\cgSE$ crashes into $\alpha$.  Also highlighted in red is the location of the first collision detection tile attachment which detects that the upward growing path is next to another $\cgSE$.  (Right) Once the collision shown in red on the left is encountered, every new layer of the left stack of $\cgSE$'s will be spaced by a vertical doubling row which causes each newly attaching $\cgSE$ in the stack to be offset from the previous by $(2,-2)$.  This offset guarantees that the left stack eventually covers the right stack, finally allowing for the growth of a perfectly rectangular layer.}
    \label{fig:stack-catch-up}
\end{figure}

%
%

%

The above arguments ensure that an exterior stack of $\cgSE$'s can continue to initiate the growth of additional layers as long as that stack is not covered by another.  Since there can be only one southeast convex corner in a rectangular layer, and therefore only one $\cgSE$, from a single stack, contained within it, we now must show that ultimately there will be only one remaining stack.  Therefore, assume that there are $n > 1$ stacks of exterior $\cgSE$'s.  We will discuss the growth of the stack furthest to the west, $s_w$ and that of the stack furthest to the east, $s_e$.

First, we note that after some finite amount of outward growth, as $s_e$ grows outward each $\cgSE$ must be attached directly to the outside of the $\cgSE$ immediately before it, i.e. there are no vertical doubling rows.  This is because neither of the 2 scenarios which result in a vertical doubling row and thus a space between the consecutive $\cgSE$'s of a stack is possible:  (1) given that there is at least one stack of exterior $\cgSE$'s to the west of it, and that it is an exterior stack, then it is geometrically impossible for a path which does not grow into a concavity of $\alpha$ (which must be the case for all paths after some finite number of layers since, as previously discussed, all concavities become covered up) to grow eastward to, and/or along the outside of, a $\cgSE$ in the easternmost stack since all paths only grow CCW (and note that this is the case for any exterior stack which has another to its west), and (2) as the easternmost stack, paths growing upward from $\cgSE$'s of $s_e$ cannot collide with other $\cgSE$'s from a stack to the north or east.  Therefore, both situations which result in vertical doubling rows are impossible for the $\cgSE$'s of $s_e$.  This means that for each path which is output from $s_e$, the southeast corner of the lowest $\cgSE$ in $s_e$ is offset from the previous by the vector $(1,-1)$.

Now, we note that after some finite amount of outward growth of $s_w$, since each additional $\cgSE$ must be placed at an $x$-coordinate which is at least 1 greater than the $\cgSE$ which preceded it, the $x$-coordinate of the eastern tiles of a $\cgSE$ in $s_w$ must be greater than or equal the the $x$-coordinates of some $\cgSE$'s in the stack immediately to its east. An important property of the stacks of $\cgSE$'s is that they all grow along the slope $(1,-1)$ (although sometimes at the vector $(2,-2)$), so no two stacks can have $\cgSE$'s which collide.  However, as soon as the $\cgSE$'s of one stack fall to the immediate south of $\cgSE$'s of a stack to its east (and again, those $\cgSE$'s cannot have paths growing into their west sides after some finite amount of outward growth), then the western stack will start having vertical doubling rows between each pair of consecutive $\cgSE$'s.  This will cause the offsets between them to be $(2,-2)$.  Assuming that there are $n$ stacks, it is possible that each of the western $n-1$ has grown to a position where it is growing over $\cgSE$'s of the stack to its east.  However, as previously mentioned, the easternmost (i.e. $s_e$) can not be growing vertical doubling rows and grows downward by the vector $(1,-1)$.  Since the paths from $s_e$ must eventually grow to $\cgSE$'s in $s_w$, there can only be one $\cgSE$ added to $s_e$ for each added to $s_w$, since the only ways that a $q$ message can be passed back to $s_e$ and initiate growth of another layer require that a $\cgSE$ be added to $s_w$ (i.e. there must be a collision with a $\cgSE$ of $s_w$ or a path initiated by it, which will cause a new layer to be initiated in $c_w$ as well). Now, as noted, each additional $\cgSE$ of $s_w$ eventually grows at a vector of $(2,-2)$ relative to the previous while those of $s_e$ can only grow at the vector $(1,-1)$.  (See Figures~\ref{fig:new-frame2-full-example2} and \ref{fig:new-frame2-full-example2-disconnect} for an example.)  As we are interested in proving that no race condition can occur which allows multiple stacks to grow indefinitely, we will show how
%
$s_w$ covers those to its east until only $s_w$ remains.  Each stack between $s_w$ and $s_e$ must eventually grow so that they are each placing $\cgSE$'s directly south of stacks which are east of them.  For them not to eventually cover $s_e$, they must grow at the same vector as $s_e$, namely $(1,-1)$ and grow layers at no greater a rate than $s_e$.  However, $s_w$ must grow layers at the same rate as $s_e$, since $s_e$ is not able to grow new layers without continued growth of $s_w$ (as previously shown), and $s_w$ must eventually grow strictly at the vector $(2,-2)$.  This ensures that $s_w$ eventually covers all stacks and becomes the sole stack of $\cgSE$'s.  Otherwise, the stacks between $s_w$ and $s_e$ can grow faster than $s_e$ and eventually cover it, but then as each becomes the new easternmost stack, its growth must slow relative to $s_w$ (as it becomes the new $s_e$ and behaves exactly as the previous), eventually ensuring that all stacks are covered by $s_w$.

The final thing to show is that the paths growing from $c_w$, the only remaining stack of $\cgSE$'s, will eventually become rectangular.    Assuming that at the point at which $s_w$ becomes the single stack, the next layer it grows is not rectangular, then there are two scenarios to consider.  The most recently placed $\cgSE$, $c_x$, grows a path CCW which eventually (1) collides with a $\cgSE$, say $c_y$, in $s_w$ which is north of $c$ in the stack (and thus was placed earlier), or (2) grows to the south of $c_x$.  In (1), each path which collides with such a $\cgSE$ will receive a $q$ signal since the path which grows outward from $c_y$ is not rectangular and therefore as previously shown must encounter a collision which ensures the propagation of a $q$ message (even if this message must pass around $\alpha$ multiple times and through multiple $\cgSE$'s).  This will cause a (horizontal) doubling row to grow along the south side of the path to the west of $c_y$.  As this doubling row must grow before another layer can grow across and collide with another $\cgSE$ in $c_w$, and that doubling row covers up one of the $\cgSE$'s in $c_w$, the vertical distance between $c_x$ and $c_y$ will be one greater than the distance between the path which grows from the $\cgSE$ that attaches to $c_x$ and the $\cgSE$ which it collides with.  Eventually, with the distance decreasing by one each time, it will become $0$, meaning that a path grows out of the north of a $\cgSE$ and back into the west of that same $\cgSE$, thus it is a rectangle.  In (2), since $c_x$ cannot initiate the growth of another layer (via the attachment of a $\cgSE$ to its outside) without its path colliding with something, there must be no $\cgSE$ to the south of $c_x$ in $s_w$ (i.e. it would have needed to be there before the collision which enabled it be placed there).  Therefore, the path must grow across the outside (i.e. on the south side) of $c_x$.  In this case, as shown in Figure~\ref{fig:collision-detection-corner-cases2} and previously discussed, a vertical doubling row will be initiated and a new $\cgSE$ will be allowed to attach to the east and south of the bottom of it.  In this way, the path which grew around and back below the $c_x$ terminates and a new $\cgSE$ initiates a row which now must be exactly a rectangular.

Thus, we have shown that all possible assembly sequences must eventually result in a rectangular row after a finite number of tile additions.


%

%

%

%

\end{proof}

\begin{figure}[htp]
\centering
    \includegraphics[width=3.5in]{images/new-frame2-full-example2}
    \caption{The full frame for the example of Figure~\ref{fig:new-frame2-full-example-begin} showing an alternate assembly sequence (from that of Figure~\ref{fig:new-frame2-full-example}) for the growth of the frame around $\alpha$ until it terminates in the first rectangular layer.  In this assembly sequence, the eastern stack of $\cgSE$'s continues growth much further than in the other.  In particular, the $\cgSE$'s of the eastern stack win the maximum number of race conditions possible, i.e. the rows which grow from them grow very quickly and $q$ messages travel back quickly, so new $\cgSE$'s are able to attach before the $\cgSE$'s of the west stack can grow past them, which could occur if a vertical doubling row from the west stack is able to quickly grow northward and collide with the south side of the $\cgSE$ which caused it to be initiated, preventing the east stack's next $\cgSE$ from attaching.  By winning these race conditions, the east stack is able to grow to a maximal depth.  Nonetheless, the depth is still bounded since the west stack can only catch up and surpass it. Light grey: $\alpha$, Green: $\cgSE$, Light blue: standard path, Dark blue: doubling row.}\label{fig:new-frame2-full-example2}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=3.5in]{images/new-frame2-full-example2-disconnect}
    \caption{The example from Figure~\ref{fig:new-frame2-full-example2} with pink portions highlighting paths which will disconnect from the layers inside of them (because each of those layers grew to the west side of a $\cgSE$), but will ultimately be unable to completely detach since the innermost $\cgSE$ on each connected path will not disconnect (since it won't receive the detach message from the north), and those $\cgSE$'s will create a $\tau$-stable connected path all the way to $\alpha$.  The red outer layer denotes the rectangular layer which can detach. Note that in this example, no pink portion of a detaching path is able to completely circle $\alpha$.}\label{fig:new-frame2-full-example2-disconnect}
\end{figure}
\qed

\input{rectangle-detach}
%
%
%
%
%
%
%
%
%
%
%
%
%

\begin{lemma}\label{lem:marking}
For each STAM system $\calT = (T,\alpha,2)$ with tile set $T$ (i.e. the frame building tile set) and input assembly $\alpha$, as a frame assembly grows, the eventual detachment of the rectangular layer will result in a single tile of the frame, one which is adjacent to a location of $\alpha$, activating a $z$ glue.
\end{lemma}

\begin{proof}
Given Lemmas~\ref{lem:rectangle-layer} and \ref{lem:rectangle-detach}, $\calT$ is guaranteed to form a rectangular frame layer which will detach.  That layer will have exactly one $\cgSE$, and before it can detach that $\cgSE$ will, by the required binding of its $p$ glue, ensure that the $\cgSE$ to which it was attached will activate a $p2'$ glue.  Once the outer layer has detached, the only tile that can attach to the now outer layer of the frame is the ``primer'' tile with $p2$.  Upon binding to the $\cgSE$'s $p2'$ glue, a cascade of messages will begin.  See Section~\ref{sec:leader} for specific details of the tiles that pass these messages, but beginning from the $\cgSE$ an $sp$ message will be sent along the entire bottom row of the assembly.  Once it reaches the western end, an `$L$' tile will attach which will cause an $spR$ message to be sent all the way back to the right side.  At this point, an `$R$' tile will attach and cause the tile it binds to to pass the $sp$ message one row to the north and then begin the process again.  This will occur until a westward traveling $sp$ signal eventually arrives at the easternmost of the southernmost $\cgSE$'s which are attached directly to $\alpha$.  Then, that $\cgSE$ is ``marked'' as the leader so that it will expose the single $z$ glue, and the $sp$ and $spR$ messages will no longer be passed.  By the facts that (1) there must be some $\cgSE$ which is the easternmost of the southernmost, (2) the $sp$ signal cannot collide with any tile of $\alpha$ before it stops at the southeasternmost $\cgSE$ (because of the fact that any signal traveling in that pattern must collide with a tile at that position of $\alpha$ and such a convex corner must have a $\cgSE$ attached to it in order for the subsequent layers to have grown, and (3) all frame building tiles can pass these messages, the correct corner gadget must receive the message.  Upon receiving the message, it will activate the necessary $z$ glue.
\qed
\end{proof}


\begin{lemma}\label{lem:full-mold}
The leader tile will initiate a message which will propagate around $\alpha$ and guarantee that for every tile location directly or diagonally adjacent to a tile in $\alpha$, layer 1 contains a tile in this location. Moreover, after all pending signals of the $br$ message have fired, the entire frame assembly detaches from $\alpha$ exposing on its interior a unique glue activated on only the leader.
\end{lemma}

\begin{proof}
All of the perimeter edges of $\alpha$ can be enumerated starting from the north edge of the leader tile and proceeding to each consecutive incident edge in the CCW direction. Then, by the construction given in Section~\ref{sec:outlining}, as the $g$ message propagates around $\alpha$ CCW starting from the leader tile, if the only tiles that are allowed to attach to the existing assembly ($\alpha$ and attached frame building tiles) are the singletons given in Section~\ref{sec:outlining}, then it is clear that each the $x$ glue on each consecutive edge enumerated in the CCW direction either binds to a tile passing the $g$ message or binds to an $x'$ tile activated by one of signals of the $g$ message. Also, by the construction presented in Section~\ref{sec:leader}, we can ensure that the north edge of the leader tile is the only edge that exposes some unique glue. Then since the $br$ message follows $g$ deactivating each $x'$ glue, after the frame disassociates from $\alpha$, the leader tile will expose a unique glue.

Therefore, to complete the proof of this lemma it suffices to show that as the $g$ message propagates around $\alpha$ CCW starting from the leader tile, if the only tiles that are allowed to attach to the existing assembly ($\alpha$ and attached frame building tiles) are the singletons given in Section~\ref{sec:outlining}.
Note that during the propagation of the $g$ message, at most a single $x'$ and $g$ glue may be exposed on an edge of the perimeter of the existing assembly. Therefore, some (possibly much smaller) shape could not bind via this $x'$ glue since it only has strength 1. Then note that if even though two such assemblies exist, they possibly expose $x$ glues and an $x'$ glue. However, these two assemblies cannot bind because the edges that expose these glues on each assembly must belong to tiles that are completely surrounded by tiles of one or more frame layers. Therefore, an assembly that exposes an $f$ and $x'$ glue on its perimeter can only bind to one of the singleton tiles or a 2-tile corner gadget described in Section~\ref{sec:outlining}.
\qed
\end{proof}

\begin{lemma}\label{lem:no-combine}
Let $\beta$ and $\gamma$ be distinct producible assemblies of $\mathcal{T}$ that each have an input assembly as a subassembly. Then $\beta$ and $\gamma$ cannot bind.
\end{lemma}

\begin{proof}

During the assembly of frame layers, many of the glues are activated (mostly for message passing purposes) are activated only after the edge that the glues are abut an edge of some tile. As long as these glues are never exposed on the perimeter of an assembly, these glues cannot allow for two producible assemblies to bind. Then, by construction, all of glues that are exposed on the exterior of an assembly have specific purpose and only allow for either some singleton tile, 2-tile gadget or 3-tile gadget to bind. For example, we use collision detection tiles/duples to minimize exposed $x'$ glues.
The one exception of this is that when layer 1 is propagating a $g$ message as described in Section~\ref{sec:outlining}, a single $x'$ glue may be exposed on the perimeter of a producible assembly. As noted in the proof of Lemma~\ref{lem:full-mold}, the only tile that may bind to a producible assembly with an input assembly as a subassembly is a singleton tile or a 2-tile corner gadget described in Section~\ref{sec:outlining}.
\qed
\end{proof}


}%

In Theorem~\ref{thm:complete-frame}, let $\mathcal{T} = (T,\sigma,2)$ be a STAM system such that $T$ is the frame building tile set given by the construction in Section~\ref{sec:frame-building} and $\sigma$ is a set of input shape assemblies.
Given an input shape assembly $\alpha$, and a TAS $\mathcal{T}$, we say that a terminal assembly $\beta$ is a \emph{completed frame assembly for} $\alpha$ \emph{ that exposes a unique glue}, $z$ say, if (after some translation of the locations in $\dom(\beta)$) there is a single finite connected component of the complement of $\dom(\beta)$ in $\Z^2$ that is equal to $\dom(\alpha)$, and moreover,  the tiles of $\beta$ at locations adjacent to locations of $\dom(\alpha)$ expose glues on the perimeter of $\beta$ such that there is a single tile (a leader tile) which exposes $z$ on a single edge of the perimeter of $\beta$.



\begin{theorem}\label{thm:complete-frame}
For any finite set $\sigma$ of input shape assemblies, if $\beta\in \termasm{T}$, then either $\beta$ is in $\sigma$, $\beta$ is a completed frame assembly for $\alpha$ that exposes a unique glue, which we denote by $z$, or $\beta$ does not expose $z$ on its perimeter (for example, the rectangular frame layer that detaches in our frame construction).
\end{theorem}

\begin{proof}
This follows directly from the Lemmas~\ref{lem:rectangle-layer},\ref{lem:rectangle-detach},\ref{lem:marking},\ref{lem:full-mold},and \ref{lem:no-combine}.
\end{proof}


intro.tex
\section{Introduction}

As a process by which molecular systems can organize themselves, autonomously forming complex structures and even performing computations, self-assembly has been shown both theoretically \cite{SolWin07,RotWin00,jCCSA,jSADS,IUSA,jSADSSF} and experimentally \cite{RothTriangles,SchWin07,MaoLabReiSee00,BarSchRotWin09,LaWiRe99,evans2014crystals} to be an extremely powerful process.  In fact, it is even the basis of many natural, especially biological, systems.  In an effort to further understand the capabilities of self-assembling systems, computational theory has been applied to design systems which perform \emph{algorithmic} self-assembly, namely self-assembly in which the constituent components are intrinsically guided by algorithmic behavior.  The systems developed have been capable of everything from extremely efficient (in terms of the numbers of unique building blocks necessary) building of shapes \cite{SolWin07,jSADSSF}, Turing machine simulations \cite{Winf98,jSADS,jCCSA}, and intrinsically universal constructions \cite{IUSA}.  In fact, those examples were all developed in a very simple model of self-assembling systems known as the abstract Tile Assembly Model (aTAM) \cite{Winf98}, in which the basic components are square \emph{tiles} which bind together, one at a time via \emph{glues} on their edges, to form assemblies.  However, in order to gain more insight into various properties of self-assembling systems, models have been developed which are extensions of the aTAM and which allow behaviors like combinations of arbitrarily large assemblies \cite{2HAMIU}, glues with repulsive forces \cite{SingleNegative}, and many others.

In this paper, we work in one such (relatively new) model, the Signal-passing Tile Assembly Model (STAM) \cite{jSignals}.  This model allows for the individual tiles, rather than being static and unchanging as in the aTAM, to each perform a constant number of operations which change the glues with which they can bind.  With these changes being spurred by binding events of the tiles, the changes of glues on individual tiles can be propagated across entire assemblies, which can be thought of as analogous to sending \emph{signals} which help direct the self-assembly process.  While the STAM has been shown to be quite powerful by previous results \cite{jSignals}, here we apply the strength of the model to a problem which has been previously studied, namely the replication of shapes \cite{RNaseSODA2010} in other models, and we prove yet more aspects of its power.

In this paper, we show how sets of arbitrary 2-dimensional hole-free shapes can be provided (at scale factor 2) to self-assembling systems within the STAM, using a single universal replicator tile set, and the resulting system will perform the parallel and exponentially increasing, unbounded replication of those shapes.  This is a dramatic improvement over previous results which required a model where multiple standalone stages and multiple assembly \emph{bins} are required, since these STAM systems are single stage, single bin systems. Furthermore, previous results placed significant restrictions on the shapes which could be replicated.  As a significant additional result which we use to produce our replication result, we provide a construction which is able to perform a complicated form of distributed \emph{leader election}, namely it is able to take as input an arbitrary 2-dimensional, hole-free shape with perfectly uniform glues on its exterior and produce an assembly which surrounds it but does so in a way in which all the portions of the shape's perimeter are covered and exactly one location on the perimeter is uniquely marked, or identified as the ``leader''.  This is especially difficult given the distributed, parallel, and asynchronous nature of tile assembly in the STAM combined with the fact that absolutely no assumptions can be made about the input shapes.  The techniques of this construction, as well as several other gadgets used in the full shape replication result, are likely to be useful in future work with the STAM.

We first present a high-level introduction to the models used in this paper, then provide our leader election construction (which we refer to as \emph{frame building}, and finally present the shape replication result.  Due to space constraints, many of the technical details of the constructions and proofs are located in the appendix.


%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

marking-a-tile.tex
\subsection{Electing a leader and casting a mold of $\alpha$}\label{sec:main-leader}

In this section, we assume that the last added layer $F$ of the frame has completed growth and is rectangular. Here we give a high-level description of what it means to elect a leader tile of layer 1 and how this is achieved.  (See Section~\ref{sec:leader} for details.) When $F$ completes the growth of a rectangle, it will pass a \emph{detach} message CW through each tile of $F$ back to the only $\cgSE$ belonging to $F$, which we denote by $CG_F$. When the $d$ message is received along the north edge of the northernmost tile of $CG_F$, it initiates a series of signals so that after $F$ detaches, the remaining assembly exposes a strength-2 glue. This strength-2 glue is exposed so that a singleton tile can bind to it. This binding event initiates the signals that ``scan'' from right to left for the first corner tile of a $\cgSE$ belonging to layer 1. Notice that this will be the easternmost tile of the southernmost tiles belonging to layer 1. The tile directly to the west of this tile is called the \emph{leader tile} of layer 1. For an overview see Figure~\ref{fig:leader-election-overview}. For leader election details, see Section~\ref{sec:leader}.

Now that a leader is elected, note that layer 1 need not completely surround $\alpha$. In other words, there may be some empty tile locations adjacent to tiles of $\alpha$. In the next section, we show how to ``complete'' layer 1 so that for every tile location adjacent to a tile of $\alpha$, this location contains a tile of layer 1. At a high-level, we describe signals and tiles that ``extend'' layer 1 of the frame to completely surround $\alpha$ by passing a $g$ message CCW around $\alpha$. Starting with the leader tile, as this message is passed, it activates glues which we use to replicate $\alpha$. The leader tile exposes a unique glue. For more detail, see Section~\ref{sec:outlining} in the appendix.

Once we have exposed glues that will allow for the replication of $\alpha$, we propagate a $br$ message through layer 1 of the frame that deactivates all of the $x'$ glues of layer 1 except for the $x'$ glue on the north edges of the leader tile. This will allow $\alpha$ to disassociate from the frame and allow the frame to be used to replicate $\alpha$.

\ifabstract
\later{

\subsection{Details for priming a frame layer and electing a leader}\label{sec:leader}

In this section, we assume that the last added layer $F$ of the frame has completed growth and is rectangular.
As discussed in the previous section, $F$ will pass a $d$ message CW through each tile of $F$ until the $\cgSE$ of $F$, which we denote by $CG_F$, is reached. When the $d$ message is received along the north edge of the northernmost tile of $CG_F$, as depicted in Figure~\ref{fig:SE-corner-gadget-tiles}, it triggers a $p$ glue to turn $\on$, which propagates a signal that turns the $p2'$ glue $\on$ on the east edge of a tile of the $\cgSE$, denoted by $CG$ say, that $CG_L$ is attached to. Moreover, the binding of the $p$ glue belonging to $CG_F$ fires signals which continue the propagation of the $d$ message and turn the $x2'$ glues of $CG_F$ $\off$.

%
%
%
%
%
%
%
%

%

\begin{figure}[htp]
\centering
  \subfloat[][Signals and glues used to enhance corner tiles of $\cgSE$'s. Once a \emph{primer tile} (shown in \ref{fig:primerTile}) attaches via the $p2'$ glue, it initiates a $sp$ message. When the $sp$ message begins propagation, the $p2'$ glue turns $\off$, and the primer tile disassociates.]{%
        \label{fig:left-right-leader-election-init}%
        \makebox[2.7in][c]{\includegraphics[scale=.33]{images/left-right-leader-election-init}}
        }%
        \quad\quad
  \subfloat[][This tile binds to a primed $frame$ layer to initiate the inward propagation of the $sp$ message which eventually reaches the a $\cgSE$ that is attached to $\alpha$. ]{%
        \label{fig:primerTile}%
        \makebox[2.7in][c]{\includegraphics[scale=.33]{images/primerTile}}
        }%
  \caption{Gadgets that initiate the propagation of a $sp$ message which ``marks'' a $\cgSE$ that is attached to $\alpha$.}
  \label{fig:frame-priming}
\end{figure}
%
%
%
%
%
%
%


Then, in order to detect a leader $\cgSE$, we enhance corner tile belonging to a $\cgSE$ with the signals depicted in Figure~\ref{fig:left-right-leader-election-init} and all of the frame building tiles discuss (including those tiles belonging to $\cgSE$) so far with signals depicted in the center figure of Figure~\ref{fig:leader-election-tiles}.

\begin{figure}[htp]
\centering
        \includegraphics[scale=.4]{images/left-right-leader-election-tiles}
  \caption{(Left) A tile that binds to the $sp'$ and $spL'$ glues on the west edge of a westernmost tile of a frame that initiate an $spR$ message. (Middle) We enhance each frame building tile with the signals depicted here. The $sp'$ glues, $spL'$ glue, and $sp'$ glue are initially $\latent$ and then triggered to turn $\on$  after an $x2'$ glue of the frame building tile binds (These $\on$ signals and the $x2'$ glue are not shown here.) (Right) A tile that binds to the $sp2$ and $spR$ glues on the east edge of an easternmost tile of a frame that propagate an $sp$ message one tile to the north of the tile to which it binds.}
  \label{fig:leader-election-tiles}
\end{figure}

Equipped with these new signals, frame tiles elect a $\cgSE$ by ``scanning'' from right to left for the first corner tile of a $\cgSE$ belonging to layer 1. Notice that this will be the easternmost tile of the southernmost tiles belonging to layer 1. For an overview see Figure~\ref{fig:leader-election-overview}. This scanning is accomplished as follows. Frame tiles can pass an $sp$ message from right to left through tiles of standard paths, doubling rows and corner gadgets. If a tile belonging to layer 1 is receives the $sp$ message, it must be a corner tile of some $\cgSE$ of layer 1 and this will be the elected $\cgSE$. If the propagation of the $sp$ message exposes an $sp$ glue on the west edge of a westernmost tile of the frame, then a singleton tile (labeled $L$ in Figure~\ref{fig:leader-election-overview}) may use this glue and an $spR$ glue to bind and initiate the propagation of an $spR$ message which propagates to the right. Notice that the $spR$ message will eventually expose an $spR$ glue on the east edge of an easternmost tile of the frame, allowing for a singleton tile (labeled $R$ in Figure~\ref{fig:leader-election-overview}) to bind via its $spR'$ and $sp2'$ glues. This fires signals which propagate the $sp$ message on tile to the north before once again propagated the $sp$ message from right to left, ensuring that eventually a $\cgSE$ of layer 1 will be elected.

}%

\begin{figure}[htp]
\centering
        \includegraphics[scale=.15]{images/left-right-leader-selection}
  \caption{An example of electing a $\cgSE$. The particular $\cgSE$ that is elected has a corner tile that is the easternmost tile of the southernmost tiles of layer 1.}
  \label{fig:leader-election-overview}
\end{figure}

\ifabstract
\later{

From Figure~\ref{fig:layer1-SEcg}, we can see that once a $sp$ message is receive by a $\cgSE$ of layer 1, it propagates a $u$ signal to the westernmost tile of that $\cgSE$. We will call this tile the \emph{leader} tile. When the $sp'$ glue of the leader tile binds, it fires signals to turn $\on$ a $z$ glue and a $y$ glue on its north edge. The purposes of these glues are described in Section~\ref{sec:rep}.

Now that a leader is elected, note that layer 1 need not completely surround $\alpha$. In other words, there may be some empty tile locations adjacent to tiles of $\alpha$. In the next section, we show how to ``complete'' layer 1 so that for every tile location adjacent to a tile of $\alpha$, this location contains a tile of layer 1.

\subsection{Details for casting a mold of $\alpha$}\label{sec:outlining}

In this section, we show how to ``extend'' layer 1 of the frame to completely surround $\alpha$ so that for every $x$ glue on $\alpha$, there is an $x'$ on some tile of the extended layer 1 that is bound to $x$.

\begin{figure}[htp]
\centering
    \includegraphics[width=2in]{images/post-collision-handling}
    \caption{ (Left) A tile capable of propagating a $g$ message around a $\alpha$ in the CCW direction. Notice that this tile can also pass a $g$ message once in each direction. Not only do we include this tile in our tile set, we enhance the frame building tiles that expose $x'$ on their left side with these signals and glues. These particular tiles propagate the $g$ message in the south-to-north direction. By appropriately rotating this figure, we can obtain signals and glues that propagate signals in the east-to-west, north-to-south, and west-to-east directions. (Right) A tile capable of propagating a $g$ message around a NE corner. We enhance the corner tile of the $\cgNE$ tiles with these signals and glues. Morover, we enhance the corner tiles of the $\cgSE$, $\cgNW$, and $\cgSW$ tiles with these signals.}
  \label{fig:post-collision-handling}
\end{figure}

Figure~\ref{fig:post-collision-handling} depicts tiles capable of propagating a $g$ message CCW around $\alpha$. When we enhance frame building tiles with the signals and glues depicted on the left in Figure~\ref{fig:post-collision-handling}, the $g'$ glue (shown in the $\on$ state in the figure) is initially $\latent$ and is turned $\on$ when $x'$ binds (this signal is not shown in the figure). Then,
as this message propagates around $\alpha$, this message is either passed through tiles of layer 1 that have previously been bound to $\alpha$, or it propagates by the attachment of a tile (depicted on the left in Figure~\ref{fig:post-collision-handling} up to rotation). With these enhancements and addition tiles, the $g$ message propagates CCW starting from the leader tile until it is passed back to the leader tile. At this point, for every $x$ glue on $\alpha$, there is an $x'$ on some tile of the extended layer 1 that is bound to $x$.

From Figure~\ref{fig:post-collision-handling}, we can notice that as the $g$ message propagates, it ensures that a $y$ glue is expose on any edge that binds to an $x$ glue of $\alpha$. Though only a single $y$ glue is signal to turn $\on$ in Figure~\ref{fig:post-collision-handling}, note that we could turn on any number of glues that we like by simply firing more signals to turn $\on$ these glues. In particular, we not only turn a $y$ glue $\on$, but we also turn a $w$ glue $\on$. The purposes of these glues will be explained in Section~\ref{sec:rep}.


Next we propagate a $br$ message through layer 1 of $\alpha$ that deactivates all of the $x'$ glues of layer 1 except for the $x'$ glue on the north edges of the leader tile. This will allow $\alpha$ to disassociate from the frame and allow the frame to be used to replicate $\alpha$. $br$ propagates as follows. Once the $g$ message is received by the leader tile, it initiates the $br$ message. In Section~\ref{sec:signal-following}, we describe a technique for designing message that ``follow'' another message.  Here we use this technique, enhancing each frame building tiles discussed so far with a $br$ message that follows the $g$ message in order. Moreover, as $br$ is passed to each consecutive tile of layer 1, it fires deactivation signals that turn $\off$ any $x'$ glues on each tile. In other words, the $br$ message is passed through each tile of layer 1 in the same order that the $g$ message was passed through each tile of layer 1. In this way, the $x'$ glues of layer 1 bound to the $x$ glues of $\alpha$ turn $\off$ with the exception of the $x'$ glue on the north edge of the leader tile. This $x'$ glue is left $\on$.

After the $br$ propagates through the tiles of layer 1 and $\alpha$ disassociates, note that the edges that had previously exposed an $x'$ glue bound to an $x$ glue of $\alpha$ now expose (or will eventually expose after pending signals fire) $z$ and $y$ glues on the north edge of the leader tile, and $w$ and $y$ glues otherwise.  After all pending signals of the frame fire, we say that the frame is a \emph{complete frame assembly for shape} $\alpha$. In Section~\ref{sec:rep}, we show how to use a completed frame for a shape to replicate arbitrary shapes.


\input{signal-following}

}%

new-frame.tex

\vspace{-5pt}
\subsection{Building layers of the frame}
\vspace{-5pt}

We now give an extremely high-level sketch of the formation of the \emph{frame}.  (See Sections~\ref{sec:layer1} and \ref{sec:frame-layers} for more details.)  Essentially, the frame grows as a series of layers of tiles which begin on (possibly many) southeast convex corners of $\alpha$ (depending on its shape) and grow counterclockwise (CCW) around $\alpha$.  A greatly simplified example of the basic tiles which can form a layer of the frame can be seen in Figure~\ref{fig:basic-convex-frame}.  Each path which forms a layer can grow only CCW, and therefore, depending on $\alpha$'s shape, may crash into a concavity of $\alpha$ (or one formed by a previous layer that the current is growing on top of).  Such \emph{collisions} are detected by a specialized set of \emph{collision detection} tiles, and an example of a collision and its detection is shown in Figure~\ref{fig:new-frame2-concave-collision1}.  The need for collision detection tiles is technical and related to the need for the exposed glues on all parts of the growing frame assembly to be minimized and carefully controlled so that multiple shapes and copies of shapes can be replicated in parallel, without separate assemblies interfering with each other.

The growth of frame layers is carefully designed so that it is guaranteed to proceed until all external openings to concavities of $\alpha$ have been filled in by partially completed layers, resulting in layers which are more and more rectangular, and eventually an exactly rectangular layer.  At this point, and only at this point, we are guaranteed to have a layer which has exactly one convex southeast corner. Due to the distributed and asynchronous nature of the assembly process, and the fact that each tile only has local information, throughout layer formation it is necessary for some layers to make local ``guesses'' that they are rectangular, and in order for that not to cause errors, a mechanism of layer detachment is used.  Basically, layers which guess they may be rectangular attempt to disconnect, but only the first truly rectangular layer can successfully detach.  At this point it activates glues on the layer immediately interior of it, which it has \emph{primed} to receive a signal from a tile which will now be free to attach since the covering exterior layer dissociates. This is then used in the unique leader election.  It is by the careful use of the ``global'' information provided by the layer detachment that the construction can proceed correctly.


\begin{figure}[htp]
\centering
    \includegraphics[width=3.0in]{images/basic-convex-frame}
    \caption{A simplified version of the tile set which grows layer 1 of the frame around $\alpha$.  The darker grey tiles represent \emph{corner gadgets} ($CG$) which form as duples (or a triple for the southeast corner gadget, $\cgSE$). Growth begins with the initial attachment of a $\cgSE$ and proceeds CCW.  There is also an analogous set with $x2'$ glues instead of $x'$ glues to form layer 2 (and all subsequent layers). Note that this is a basic, beginning tile set to which we will add additional signals and tiles throughout the construction.}\label{fig:basic-convex-frame}
\end{figure}

\ifabstract
\later{

\subsection{Assembly of layer 1 tiles}\label{sec:layer1}

%
First we will describe the tiles that initially attach to $\alpha$, starting the frame building process. These tiles are relatively simpler than the tiles of layers that follow. We refer to the tiles that assemble the frame as the \emph{frame building tiles}. Moreover, as the frame assembles, any tile that is located at positions directly or diagonally adjacent to a tile of $\alpha$ is referred to as a \emph{layer 1} tile and as a \emph{layer 2} tile otherwise.

We will describe how the tiles that belong to layer 1 begin assembly

\begin{observation} \label{obs:secExists}
Every input assembly has at least one convex corner of each type.  This follows directly from the definition of a shape formed by an assembly. For instance, starting from an arbitrary point on the perimeter of any valid $\alpha$, follow the perimeter in a CCW direction until returning at the original location, after having traversed the entire perimeter of $\alpha$.  This must be possible because $\alpha$ is a connected 2-D shape and the perimeter of $\alpha$ must be a continuous line.  In order to move in a full circle around the perimeter which is composed of unit squares, it is necessary to make at least one turn in each direction (N, W, S, and E), and each such turn occurs at a convex corner $\secon$, $\necon$, $\nwcon$, and $\swcon$, respectively.
\end{observation}

\begin{enumerate}
    \item The first tile attachment to $\alpha$ must consist of a $\cgSE$ attaching to a $\secon$ corner of $\alpha$.  (See Figure~\ref{fig:basic-convex-frame}.) Since $\alpha$ may be non-rectangular, it may have multiple $\secon$ corners, but by the definition of a shape it must have at least one, and by the fact that every side of every tile on the perimeter of $\alpha$ exposes an $x$ glue, a $\cgSE$ can attach to the single tile of each $\secon$.  Therefore, one or more such attachments occur.
%
The tiles of a $\cgSE$ are described in Figure~\ref{fig:layer1-SEcg}. By Observation~\ref{obs:secExists}, at least one $\cgSE$ binds to $\alpha$, initiating the assembly of a frame.


\begin{figure}[htp]
\centering
    \includegraphics[width=4in]{images/layer1-SEcg}
    \caption{The 3 tiles that make up a layer 1 $\cgSE$ (a $\cgSE$ with consisting of layer 1 tiles). These tiles form a $\cgSE$ that can bind to two exposed $x$ glues. (Left) A $\cgSE$ tile shown labeled $A$ in Figure~\ref{fig:secgCases}. (Middle) A $\cgSE$ tile shown labeled $B$ in Figure~\ref{fig:secgCases}. (Right) A $\cgSE$ tile shown labeled $C$ in Figure~\ref{fig:secgCases}.  Note that after the tile a $\cgSE$ binds to $x$ glues, it triggers $x2$ glues to turn $\on$.}\label{fig:layer1-SEcg}
\end{figure}

    \item From each attached $\cgSE$, a single-tile-wide path grows CCW with each layer 1 tile binding to the $x$ glue on $\alpha$ and the output $f$ glue of the immediately preceding tile, forming what we call a \emph{standard path}.  In this way, we say the the $f$ message is passed CCW through a standard path of the frame.  The \emph{forward} direction for the path follows the direction of its growth, and its \emph{backward} direction is the opposite.  The \emph{back} of a frame tile is the side which served as input during its initial attachment with the glue $f'$.  The \emph{front} is the side opposite the back.  Similarly, the \emph{left} is the input side with the input glue $x'$, and the \emph{right} side is the side opposite the left.  Note that we use these terms to talk about directions relative to individual tiles, and the cardinal directions N,E,S,W to talk about absolute directions. The tiles that assemble these standard paths are described in Figure~\ref{fig:layer1-east-edge-crawler}.

\begin{figure}[htp]
\centering
    \includegraphics[width=1in]{images/layer1-east-edge-crawler}
    \caption{A tile that binds to an $x$ glue and an $f$ glue. The standard path that this tile assembles begins growth from a $\cgSE$. Then, as the standard path grows one tile attachment at a time, each consecutive tiles that binds is located one tile location above the previously binding tile. That is, these tiles grow standard paths along the east edges of $\alpha$. Tile types that can grow standard paths along north, west, or south edges of $\alpha$ are obtained by appropriately rotating the tile type depicted in this figure.}\label{fig:layer1-east-edge-crawler}
\end{figure}

    \item A standard path of layer 1 can continue growing along straight edges of $\alpha$, with each tile using an $x'$ glue as input on its left side, and an $f'$ glue as input in its back side.  As each tile binds, it activates an $f$ glue on its front side, thus allowing the path to continue along straight edges.

    \item When arriving at a NE, NW, or SW convex corner, a simple 2-tile corner gadget (denoted by $\cgNE$, $\cgNW$, and $\cgSE$ respectively) allows for continued growth around the convex corner while continuing to pass the $f$ message. The tiles of a $\cgNE$ are described in Figure~\ref{fig:layer1-NE-gadget}. Moreover, when arriving at a SE convex corner, the middle and left tile of Figure~\ref{fig:layer1-SEcg} allows for continued growth around the convex corner while continuing to pass the $f$ message.

\begin{figure}[htp]
\centering
    \includegraphics[width=3in]{images/layer1-NE-gadget}
    \caption{The 2 tiles that make up a $\cgNE$ that can bind to an $x$ glue and an $f$ glue. The 2-tile gadget formed by these tiles binds to an assembly effectively turning a $\necon$. The $f$ message now propagates from right to left. Moreover, once a $\cgNE$ binds, signals trigger $x2$ glues to turn $\on$. To obtain a $\cgNW$ or a $\cgSW$, rotate the tiles shown in this figure appropriately CCW.}\label{fig:layer1-NE-gadget}
\end{figure}

    \item A standard path of tiles must eventually terminate in one of two situations:
        \begin{enumerate}
        \item It collides with (i.e. a tile of the path attaches so that its front side is immediately adjacent to another tile) some tile of $\alpha$ or a frame tile. In this case, the standard path simply terminates.

        \item It grows to a position adjacent to a $\cgSE$ at position 7 as shown in Figure~\ref{fig:secgCases}.  In this case, the standard path terminates since the tile $C$ in Figure~\ref{fig:secgCases} does not expose an $x$ glue on its south edge. \label{item:layer1-terminates-special-case}

\begin{figure}[htp]
\centering
    \includegraphics[width=1in]{images/secgCases}
    \caption{The tile locations in relation to a $\cgSE$.}\label{fig:secgCases}
\end{figure}


       \item It collides with a $\cgSE$ from position 2 as shown in Figure~\ref{fig:secgCases}.
       %

        \end{enumerate}


\end{enumerate}


Layer 1 tiles assemble a frame by propagating an $f$ signal CCW around $\alpha$. Note that when $\alpha$ is not a rectangle, the growth of some standard paths of layer 1 may be blocked by tiles of $\alpha$. On the other hand, if $\alpha$ is a rectangle, then layer 1 tiles assemble a single tile wide rectangular frame around $\alpha$. In either case, layer 1 exposes $x2$ glues which will allow for addition frame tiles to attach, forming addition layers of the frame. The assembly additional layers is given in the next section.

\subsection{Assembly of additional frame layers}\label{sec:frame-layers}

In this section, we will show how additional layers assemble. We will see that these layers assemble in a similar manner to layer 1, with the exception that the tiles that assembly additional layers are enhanced so that as a given layer is assembling, it is capable of ``detecting'' when a it not a complete rectangular frame layer. That is, each tile has been equipped with glues and signals that check if any part of $\alpha$ or some frame layer has a tile located to its right side. When a layer detects that it is not a rectangle, it allows for an addition layer to attach by exposing more $x2$ glues. Moreover, each tile is enhanced with glues and signals so that when a standard path of tiles forms by starting from a $\cgSE$ and ending at a (possibly different) $\cgSE$, the tiles of this portion standard path ``guess'' that belong to a rectangular frame layer and propagate a message that attempts to turn left $x2'$ glues of this frame layer $\off$, thus attempting to detach this frame layer. Later we will show that such a frame layer cannot detach without actually being a rectangular frame layer.

At a high-level, each consecutive layer that is added is due to the fact that a previous layer has detected that it is not a rectangular layer and with each additional layer, more and more concavities ``fill in''
(See Figures~\ref{fig:new-frame2-full-example-begin},\ref{fig:new-frame2-full-example}, and \ref{fig:new-frame2-full-example-disconnect}.)
We will show that after some finite number of layers form the last layer never detects that it is not a rectangle and propagates a detach message that eventually causes this last layer to disassociate. Here we see the use of disassociate to ``learn something global'' about a shape (namely, that it is a rectangle). We will then use the fact that a rectangle has a single $\secon$ to ``elect a leader tile''. This leader election is described in Section~\label{sec:leader}. Now, we present the assembly of additional layers.


\begin{figure}[htp]
\centering
    \includegraphics[width=3.5in]{images/new-frame2-full-example-begin}
    \caption{The early stages of a full example showing the growth of the frame around $\alpha$.  Light grey: $\alpha$, Green: $\cgSE$, Light blue: standard path.}\label{fig:new-frame2-full-example-begin}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=3.5in]{images/new-frame2-full-example}
    \caption{The full frame for the example of Figure~\ref{fig:new-frame2-full-example-begin} showing the growth of the frame around $\alpha$ until it terminates in the first rectangular layer. Doubling rows are shown as dark blue.}\label{fig:new-frame2-full-example}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=3.5in]{images/new-frame2-full-example-disconnect}
    \caption{The example from Figure~\ref{fig:new-frame2-full-example} with pink portions highlighting paths which will disconnect from the layers inside of them (because each of those layers grew to the west side of a $\cgSE$), but will ultimately be unable to completely detach since the innermost $\cgSE$ on each connected path will not disconnect (since it won't receive the detach message from the north), and those $\cgSE$'s will create a $\tau$-stable connected path all the way to $\alpha$.  The red outer layer denotes the rectangular layer which can detach, and the entire segment of the longest connected path which attempts to detach is shown in black for highlighting. This path spirals around the perimeter of $\alpha$ several times before stopping at a segment which does not detach.}\label{fig:new-frame2-full-example-disconnect}
\end{figure}

\begin{enumerate}
	\item The first tiles that may attach to layer 1 tiles fall into two cases:
	\begin{enumerate}
		\item The tile attachment to layer 1 consists of a 3-tile $\cgSE$ attaching to a $\cgSE$ from that exposes $x2$ glues. The signals that pertain to this case are described in Figure~\ref{fig:SE-corner-gadget-tiles}.
		\item Some standard row terminated growth using $x$ glues as described in Case~\ref{item:layer1-terminates-special-case}. In this case, the tile attachment to layer 1 consists of a singleton tile attaching to a $\cgSE$ at location 6 in Figure~\ref{fig:secgCases} relative to this $\cgSE$ of layer 1. This tile is described in Figure~\ref{fig:south-edge-crawling-tile}.
	\end{enumerate}
	
\begin{figure}[htp]
\centering
    \includegraphics[width=5in]{images/SE-corner-gadget-tiles}
    \caption{Signals and glues for 3 tiles that make up a $\cgSE$. We enhance the 3 tiles of Figure~\ref{fig:layer1-SEcg} with the signals and glues shown here from left to right respectively. Here we again only depicting some of the signals of these tiles. We will add addition glues and signals in the frame construction.}\label{fig:SE-corner-gadget-tiles}
\end{figure}


\begin{figure}[htp]
\centering
    \includegraphics[width=1.5in]{images/south-edge-crawling-tile}
    \caption{Signals and glues for a tile that grows standard paths of some layer 2. We enhance the corresponding layer 1 tile (a rotated version of the layer 1 tile is shown in Figure~\ref{fig:layer1-east-edge-crawler}) with the signals and glues shown here. Again, as we will add additional glues and signals to this tile.}\label{fig:south-edge-crawling-tile}
\end{figure}

    \item From each attached tile of $\layertwo$, a single-tile-wide path grows CCW with each tile binding to the $x2$ glue of a previous layer or $x$ glue on $\alpha$ and the output $f$ glue of the immediately preceding tile. As in the assembly of layer 1, we call this the formation of a \emph{standard path} and use analogous notions of back, front, left and right sides. Hence, standard paths grow along straight edges of either $\alpha$ or previous layers that have exposed $x2$ glues on their right sides, with each tile using an $x'$ or $x2'$ glue as input on its left side, and an $f'$ glue as input in its back side.  As each tile binds, it activates an $f$ glue on its front side, thus allowing the path to continue along straight edges. The glues and signals pertaining to the case where a standard path tile binds to an $x2$ glues are described in Figures~\ref{fig:south-edge-crawling-tile} and~\ref{fig:new-frame2-tile}.

\begin{figure}[htp]
\centering
    \includegraphics[width=1.5in]{images/new-frame2-tile}
    \caption{A frame tile which grows along a northern edge and which has been enhanced to detect collisions via collision detection tiles (see Figure~\ref{fig:collision-detection-tiles}) and pass the \emph{quit} (i.e. $q$) message as needed.  Also, once it is able to determine it is on a quitting path (via attachment to the $c$ glue or reception of a $q$ message), it deactivates its collision detection $c$ glue and activates the $x2$ glue which will allow another layer to grow over it. This tile is also enhanced to pass the \emph{detach} (i.e. $d$) message CW. Note that this tile deactivates the left $x2'$ glue when the $d$ message is received, and also that the $d$ and $d'$ glues are strength-2 glues.}\label{fig:new-frame2-tile}
\end{figure}

	\item When arriving at a NE, NW, or SW convex corner that exposes two $x2$ glues, a simple 2-tile corner gadget (denoted by $\cgNE$, $\cgNW$, and $\cgSE$ respectively) allows for continued growth around the convex corner while continuing to pass the $f$ message. The signals for a $\cgNE$ are described in Figure~\ref{fig:NE-corner-gadget-tiles}.

\begin{figure}[htp]
\centering
    \includegraphics[width=4in]{images/NE-corner-gadget-tiles}
    \caption{The 2 tiles that make up a $\cgNE$ that can bind to an $x2$ glue and an $f$ glue.}\label{fig:NE-corner-gadget-tiles}
\end{figure}

	\item As a tiles of a layer bind to $x2$ glues, they trigger $c$ glues to turn $\on$. Corner gadgets also trigger $c_{dir}$ glues to turn $\on$, where $dir$ can be $se$, $sw$, $ne$ or $nw$. During the assembly of a layer, if any of the singleton tiles or duples depicted in Figures~\ref{fig:collision-detection-tiles},~\ref{fig:collision-detection-corner-cases}, or~\ref{fig:standard-row-nonquitting-cgse} bind, then any tile of a frame layer that allows one of these singleton tiles or duples to bind cannot be rectangular. For examples of various cases where one of these singleton or duple tiles bind, see Figures~\ref{fig:new-frame2-concave-collision1},~\ref{fig:new-frame2-duple-detect-collision},~\ref{fig:new-frame2-single-detect-collision}, and~\ref{fig:special-collision-detection}.

\begin{figure}[htp]
\centering
    \includegraphics[width=3.5in]{images/collision-detection-tiles}
    \caption{The tiles which, individually or after forming duples, are able to bind to any frame layer which  is not rectangular.  Note that there are also analogous versions of all of these tiles where the $x2'$ glues are replaced by $x'$ glues so that collisions between frame layers and $\alpha$ as well as between frame layers can be detected.}\label{fig:collision-detection-tiles}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=3.5in]{images/collision-detection-corner-cases}
    \caption{While the collision detection duples/tiles of Figure~\ref{fig:collision-detection-tiles} detect collisions with $\alpha$ and frame layers that present $x2$ glues, the tiles depicted here detect collisions of frame layers with other frame layers using $c$ and $c_{dir}$ glues where $dir$ is either $se$, $sw$, $ne$, or $nw$. See Figure~\ref{fig:special-collision-detection} for examples of how these detection duples/tiles are used.}\label{fig:collision-detection-corner-cases}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=0.5in]{images/standard-row-nonquitting-cgse}
    \caption{An example of detection of the case where a standard row terminates in position 7 in Figure~\ref{fig:secgCases}. By rotating this tile, we can detected similar collisions with $\cgNE$'s, $\cgNW$'s, and $\cgSW$'s.}
    \label{fig:standard-row-nonquitting-cgse}
\end{figure}

	\item Any tile belonging to a frame layer that binds via a $c$ or $c_{dir}$ glue begins the forward and backward propagation of a \emph{quit} ($q$) message.  It also turns off its $c$ glue to which the collision detection tile attached (causing it to detach) and turns on an $x2$ glue on that side, thus allowing for another frame layer tile to bind via this $x2$ glue. Every tile in the path which receives the $q$ message turns off the $c$ glue on its right side and turns on an $x2$ glue there, and continues the propagation of $q$ in the CW and CCW directions.

} %

\begin{figure}[htp]
\centering
    \includegraphics[width=5.0in]{images/new-frame2-concave-collision1}
    \caption{Depiction of a path colliding into a concavity, which is detected by the attachment of a collision detection tile.  Upon connecting, the collision detection tile initiates a $q$ message which causes all outward $c$ glues to deactivate and $x2$ glues to turn on.  This also causes the collision detection tile to fall off.}
    \label{fig:new-frame2-concave-collision1}
\end{figure}

\ifabstract
\later{

%
%
%
%
%

\begin{figure}[htp]
\centering
    \includegraphics[width=2.0in]{images/new-frame2-duple-detect-collision}
    \caption{An example of a collision detection by a collision detection duple (which attached, initiated the $q$ message, then detached).}
    \label{fig:new-frame2-duple-detect-collision}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=2.0in]{images/new-frame2-single-detect-collision}
    \caption{An example of a collision detection by a collision detection tile (which attached, initiated the $q$ message, then detached), while the path is still growing into a concavity.}
    \label{fig:new-frame2-single-detect-collision}
\end{figure}



\begin{figure}[htp]
\centering
  \subfloat[][Collision detection enabled by a collision detection tile like the one in Figure~\ref{fig:standard-row-nonquitting-cgse}.]{%
        \label{fig:new-frame2-special-detect-collision}%
	        \includegraphics[width=1.5in]{images/new-frame2-special-detect-collision}
        }%
        \quad\quad
  \subfloat[][Collision detection enabled by a collision detection duple which attaches to a $\cgNW$, similar to those shown in Figure~\ref{fig:collision-detection-corner-cases}.]{%
        \label{fig:new-frame2-special-detect-collision2}%
        		\includegraphics[width=1.5in]{images/new-frame2-special-detect-collision2}
        }%
  \caption{Examples of special cases of collision detection.}
  \label{fig:special-collision-detection}
\end{figure}

	\item The $q$ message will then pass through all tiles on that path back to the $\cgSE$ which initiated the path.  That $\cgSE$ will now have the information that the path was not a rectangle (i.e. it encountered some concavity), so it will activate glues which allow a $\cgSE$ to attach to its back and begin growth of a new layer using tiles. It will also continue the propagation of the $q$ message to any path which grows into it so that that path will initiate growth of a \emph{doubling row} to its south. In Figure~\ref{fig:doubling-row-example}, a doubling row is shown in dark blue. (The structure and function of the doubling row will be discussed later.)  To initiate the growth of a doubling row, when a $\cgSW$ receives a $q$ message, it turns $\on$ a strength-2 $dri$ (\emph{doubling row initiator}) glue. This allows for the growth of a doubling row which will grow along the south border of the layer. This in effect makes the south of the layer row 2 rows wide.

\begin{figure}[htp]
\centering
    \includegraphics[width=2.0in]{images/doubling-row-example}
    \caption{A schematic depiction of the case where a doubling row forms.}
    \label{fig:doubling-row-example}
\end{figure}




	\item When a row of tiles (belonging to either a standard path or a doubling row) of a layer grows along the south perimeter of another frame layer, if the row places a tile at location 3 in Figure~\ref{fig:secgCases} relative to some corner gadget. This case is described in Figure~\ref{fig:vdr1}.		


	\item As a row of tiles grows along eastern edges of some frame layer, if this row of tiles places a tile at location 7 in Figure~\ref{fig:secgCases}, then a \emph{vertical doubling row} forms as described in Figure~\ref{fig:vdr2}. The purpose of these vertical doubling rows will be described later.


\begin{figure}[htp]
\centering
    \includegraphics[width=3.0in]{images/vdr1}
    \caption{For convenience, all references to a location number in this caption refer to Figure~\ref{fig:secgCases} relative to the green $\cgSE$ shown in each figure. We enhance our frame building tiles so that when a tile of a row growing along the south edges of a frame layer place a tile, $t$, at location 3, the tile of the $\cgSE$, $CG$ say, just north of $t$ exposes a $cg$ glue (top right). The north edge of $t$ is given a $cg'$ glue so that when the $cg'$ glue binds, it fires a $vdr$ (vertical doubling row) message that propagates upward through north edges (bottom left). As this message is propagated, consecutive tiles of a vertical doubling row attach growing a path of tiles upward (bottom right). A vertical doubling row does not turn a northeast corner, instead, each $\cgNE$ has a $c_{ne}$ glue so that when a tile, call it $t$, of a vertical doubling row binds along the east edge of the easternmost tile of a $\cgNE$, $c_{ne}$ activates an $x2$ glue on the north edge of $t_v$. Moreover, in this case, instead of propagating a $q$ message CCW from the tiles of $CG$, a $q2$ message is propagated. When this message is passed to the westernmost tile of a $\cgSW$, it activates an $x2$ glue (as opposed to the activation of a $dri$ glue as in the case where a $q$ message is passed to the westernmost tile of the $\cgSW$) on the north edge of this tile.}
    \label{fig:vdr1}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=4.0in]{images/vdr2}
    \caption{Again, for convenience, all reference to a location number in this caption refer to Figure~\ref{fig:secgCases} relative to the green $\cgSE$ shown here. We also number the figures here 1 through 5 in order from left to right. When a standard row places a tile in location 7, a singleton tile, $ch$, detects this to be the case (shown in figure 1) by cooperatively binding to $c2$ and $cg$ glues that we enhance our frame tiles with. The binding of this singleton tile initiates a $q2$ message that is passed CCW through a layer that turns $\off$ $c$ and $c2$ glues (allowing for the detachment of $ch$) and turns $\on$ $x2$ glues on east edges (figure 2). When this message is received by the corner tile of the first $\cgSE$ that it reaches, instead of activating an $x2$ glue on the east edge, it activates a $vdr$ glue (figure 3). $vdr$ initiates the growth of a vertical doubling row (shown as the blue column in figure 4) by propagated a $vdr$ message upward. The $vdr$ message is also propagated downward allowing for the attachment of a singleton tile (the tile with two $x2$ glues in figure 4 and 5). When the $vdr$ message is passed to this singleton tile, it activates south and east $x2$ glues that allow for another $\cgSE$ to attach (figure 5).}
    \label{fig:vdr2}
\end{figure}

%
%

        \item When a frame layer tile is placed adjacent to a $\cgSE$ in position 2 as shown in Figure~\ref{fig:secgCases}, and this $\cgSE$ does not expose $x2$ glues, as long as the $\cgSE$ does not belong layer 1, the appropriate collision detection duple in Figure~\ref{fig:rectangle-detection-duple} will attach which will cause the initiation of a $d$ (\emph{detach}) message which will be propagated backward through the path, starting within the $\cgSE$ so that the $\cgSE$ binds to the colliding path tile using a $d$ glue, all of which are strength-2. (A $\cgSE$ of layer 1 would not have been able to attach to a collision detection gadget and will initiate the growth of layer 2 on its back.)  Each tile/duple in the path that receives the $d$ message turns the $x2'$ glue on its left side $\off$, thus detaching it from the layer that it grew on top of.  When a $d$ message arrives at the north side of a $\cgSE$, that $\cgSE$ deactivates the $x2'$ glues with which it initially attached to the assembly.\label{item:detach}

\begin{figure}[htp]
\centering
    \includegraphics[width=1.0in]{images/rectangle-detection-duple}
    \caption{A duple that attaches to a tile of a standard path and the westernmost tile of a $\cgSE$ that initiates the $d$ (detach) message. This duple attaches in cases when a layer may be a rectangle.}
    \label{fig:rectangle-detection-duple}
\end{figure}

\end{enumerate}

In Section~\ref{sec:frame-proof}, we will see that after some finite number of layers have assembled around $\alpha$, the last layer assembled will be a rectangle. In the case where a frame layer is rectangular, the $\cgSE$ which initiates the $d$ message, call it $CG_d$, will eventually receive this message on its north side, turning off its $x2$ glues. Before turning $\off$ this $\cgSE$'s $x2'$ glues, we first \emph{prime} the layer that $CG_d$ is attached to. At a high-level, priming exposes a glue on the frame layer that $CG_d$ is attached to which allows a special singleton tile to bind, triggering the signals that will elect a leader (a single special tile that will initiate shape replication) belong to layer 1. The $d$ message described in Case~\ref{item:detach} will eventually turn all left $x2'$ glues exposed by this layer $\off$, allowing $CG_d$ to disassociate and expose the glue turned $\on$ in the priming process. Priming a layer and its purpose as well as electing a leader tile belong to layer 1 are described in the next section.

} %

prelims.tex
\vspace{-20pt}
\section{Preliminaries}\label{sec:prelims}
\vspace{-10pt}

Here we provide informal descriptions of the models and terms used in this paper.  Due to space limitations, the formal definitions can be found in \cite{Signals3DArxiv}.

\ifabstract
\later{

\vspace{-5pt}
\section{Appendix}
\subsection{Informal definition of the 2HAM}
\vspace{-5pt}

The 2HAM \cite{AGKS05g,DDFIRSS07} is a generalization of the abstract Tile Assembly Model (aTAM) \cite{Winf98} in that it allows for two assemblies, both possibly consisting of more than one tile, to attach to each other. Since we must allow that the assemblies might require translation before they can bind, we define a \emph{supertile} to be the set of all translations of a $\tau$-stable assembly, and speak of the attachment of supertiles to each other, modeling that the assemblies attach, if possible, after appropriate translation.
%
We now give a brief, informal, sketch of the $d$-dimensional 2HAM, for $d \in \{2,3\}$, which is normally defined as a 2D model but which we extend to 3D as well, in the natural and intuitive way.


A \emph{tile type} is a unit square if $d=2$, and cube if $d=3$, with each side having a \emph{glue} consisting of a \emph{label} (a finite string) and \emph{strength} (a non-negative integer).   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}.
A \emph{supertile} is (the set of all translations of) a positioning of tiles on the integer lattice $\Z^d$.  Two adjacent tiles in a supertile \emph{interact} if the glues on their abutting sides are equal and have positive strength.
Each supertile induces a \emph{binding graph}, a grid graph whose vertices are tiles, with an edge between two tiles if they interact.
The supertile 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 supertile is stable if at least energy $\tau$ is required to separate the supertile into two parts.

Given a set of tiles $T$, define a \emph{state} $S$ of $T$ to be a multiset of supertiles, or equivalently, $S$ is a function mapping supertiles of $T$ to $\N \cup \{\infty\}$, indicating the multiplicity of each supertile in the state. We therefore write $\alpha \in S$ if and only if $S(\alpha) > 0$.

A \emph{(two-handed) tile assembly system} (\emph{TAS}) is an ordered triple $\mathcal{T} = (T, S, \tau)$, where $T$ is a finite set of tile types, $S$ is the \emph{initial state}, and $\tau\in\N$ is the temperature.  For notational convenience we sometimes describe $S$ as a set of supertiles, in which case we actually mean that $S$ is a multiset of supertiles with one count of each supertile. We also assume that, in general, unless stated otherwise, the count for any single tile in the initial state is infinite.

Given a TAS $\calT=(T,\tau)$, a supertile is \emph{producible}, written as $\alpha \in \prodasm{T}$, if either it is a single tile from $T$, or it is the $\tau$-stable result of translating two producible assemblies without overlap. Note that if $d=3$, or if $d=2$ but it is explicitly mentioned that \emph{planarity} is to be preserved, it must be possible for one of the assemblies to start infinitely far from the other and by merely translating in $d$ dimensions arrive into a position such that the combination of the two is $\tau$-stable, without ever requiring overlap.  This prevents, for example, binding on the interior of a region completely enclosed by a supertile.
A supertile $\alpha$ is \emph{terminal}, written as $\alpha \in \termasm{T}$, if for every producible supertile $\beta$, $\alpha$ and $\beta$ cannot be $\tau$-stably attached.
A TAS is \emph{directed} if it has only one terminal, producible supertile.

}%

\vspace{-5pt}
\subsection{Informal description of the STAM}
\vspace{-5pt}

(Note that the STAM is an extension of the 2HAM, and an informal description of the 2HAM can be found in the appendix.)
In the STAM, tiles are allowed to have sets of glues on each edge (as opposed to only one glue per side as in the TAM and 2HAM).  Tiles have an initial state in which each glue is either ``$\texttt{on}$'' or ``$\texttt{latent}$'' (i.e. can be switched $\texttt{on}$ later).  Tiles also each implement a transition function which is executed upon the binding of any glue on any edge of that tile.  The transition function specifies, for each glue $g$ on a tile, a set of glues (along with the sides on which those glues are located) and an action, or \emph{signal} which is \emph{fired} by $g$'s binding, for each glue in the set.  The actions specified may be to: 1. turn the glue $\texttt{on}$ (only valid if it is currently $\texttt{latent}$), or 2. turn the glue $\texttt{off}$ (valid if it is currently $\texttt{on}$ or $\texttt{latent}$).  This means that glues can only be $\texttt{on}$ once (although may remain so for an arbitrary amount of time or permanently), either by starting in that state or being switched $\texttt{on}$ from $\texttt{latent}$ (which we call \emph{activation}), and if they are ever switched to $\texttt{off}$ (called \emph{deactivation}) then no further transitions are allowed for that glue.  This essentially provides a single ``use'' of a glue (and the signal sent by its binding).  Note that turning a glue $\texttt{off}$ breaks any bond that that glue may have formed with a neighboring tile. Also, since tile edges can have multiple active glues, when tile edges with multiple glues are adjacent, it is assumed that all matching glues in the $\texttt{on}$ state bind (for a total binding strength equal to the sum of the strengths of the individually bound glues).  The transition function defined for each tile type is allowed a unique set of output actions for the binding event of each glue along its edges, meaning that the binding of any particular glue on a tile's edge can initiate a set of actions to turn an arbitrary set of the glues on the sides of the same tile either $\texttt{on}$ or $\texttt{off}$.

As the STAM is an extension of the 2HAM, binding and breaking can occur between tiles contained in pairs of arbitrarily sized supertiles.  In order to allow for physical mechanisms which implement the transition functions of tiles but are arbitrarily slower or faster than the average rates of (super)tile attachments and detachments, rather than immediately enacting the outputs of transition functions, each output action is put into a set of ``pending actions'' which includes all actions which have not yet been enacted for that glue (since it is technically possible for more than one action to have been initiated, but not yet enacted, for a particular glue). Any event can be randomly selected from the set, regardless of the order of arrival in the set, and the ordering of either selecting some action from the set or the combination of two supertiles is also completely arbitrary.  This provides fully asynchronous timing between the initiation, or firing, of signals (i.e. the execution of the transition function which puts them in the pending set) and their execution (i.e. the changing of the state of the target glue), as an arbitrary number of supertile binding events may occur before any signal is executed from the pending set, and vice versa.  %


An STAM system consists of a set of tiles and a temperature value.  To define what is producible from such a system, we use a recursive definition of producible assemblies which starts with the initial tiles and then contains any supertiles which can be formed by doing the following to any producible assembly:  1. executing any entry from the pending actions of any one glue within a tile within that supertile (and then that action is removed from the pending set), 2. binding with another supertile if they are able to form a $\tau$-stable supertile, or 3. breaking into $2$ separate supertiles along a cut whose total strength is $< \tau$.

%

The STAM, as formulated, is intended to provide a model based on experimentally plausible mechanisms for glue activation and deactivation. %
%
%

A detailed, technical definition of the STAM model is provided in \cite{Signals3DArxiv}.

\input{frame-conventions}


rectangle-detach.tex

\begin{lemma}\label{lem:rectangle-detach}
For each STAM system $\calT = (T,\alpha,2)$ with tile set $T$ (i.e. the frame building tile set) and input assembly $\alpha$, as a frame assembly grows, no subassembly containing tiles of $\frametiles$ can completely detach from the assembly unless it consists of a path which forms a complete and exact rectangle.  Furthermore, the first such rectangular path will detach and then no further layers will grow.
\end{lemma}

\begin{proof}
To prove Lemma~\ref{lem:rectangle-detach}, we first show that no frame path $p$ which is non-rectangular can ever detach.  As mentioned in the proof of Lemma~\ref{lem:rectangle-layer}, every frame tile (i.e. those in $\frametiles$) which attaches to the assembly does so by making one of its initial bonds to $\alpha$, a tile of a layer which is between it and $\alpha$, or a doubling row.  If it is a $\cgSE$, it makes two such bonds, and otherwise it makes one of its initial bonds to another tile of the same path.  Thus, before any glue deactivations, all tiles are stably attached to each other and the assembly to their inside (i.e. left sides).  The only way for a frame tile to detach, therefore, is for one or more glues to be deactivated, and the only glues that can be deactivated on a frame tile are (1) the $x2$ glue binding it to the tile to its inside, and (2) the $c$ glue on its outside (i.e. right side) which can attach to a collision detection tile.  Since the $c$ glue only binds (temporarily, before being deactivated) to a collision detection tile, its deactivation is not sufficient to allow a frame tile - possibly along with an attached subassembly - to detach.  Therefore, we now discuss the deactivation of the $x2$ glue, which occurs only as a $d$ message is passed CW through a path.  A $d$ message is initiated only when a frame path grows around three convex corners (NE, NW, and SW) and then places a tile so that its front (east) side is adjacent to the west side of a $\cgSE$, and then a special collision detection duple attaches to that $\cgSE$ and path tile.  This binding causes the west tile of the $\cgSE$ to activate a $d$ glue on its west side, which attaches to the $d'$ glue on the east of the colliding path tile.  This initiates the passing of the $d$ message through the entire path, back to the $\cgSE$ which initiated it.  Each tile which the $d$ message passes through deactivates the $x2$ glue on its left side and continues passing the message.  It is important to note that the $d$ and $d'$ glues are strength-2, so as a path detaches from the tiles inside of it, the tiles of the path itself remain stably connected to each other, as well as to the $\cgSE$ which initiated the $d$ message. (Note, the frame tiles which bind to $\alpha$, i.e. those of layer 1, don't pass the $d$ message, so the innermost layer doesn't detach following this procedure.)  In this way, the tiles in a path can detach from the assembly inside of them, but they remain bound to the $\cgSE$ which initiated the $d$ message.  The only way that a $\cgSE$ will deactivate its $x2$ glues is if it receives a $d$ message from its north, and it can only do that once it has already sent a $d$ message out its west side (since the glue that receives the signal from the north is only activated after the $d$ glue on its west has bound).  While a series of paths and $\cgSE$'s to which they are attached may cause a $d$ message to make multiple CW passes around the assembly, causing most of that connected path to detach from the inner assembly, that path is ultimately still connected to the most CCW $\cgSE$ which initiated a $d$ message on that path.  However, any path which is not part of a layer which is not perfectly rectangular must, by following this path, be connected to a $\cgSE$ whose north-growing path terminated in a collision.  That means that that final $\cgSE$ must never be able to receive a $d$ message from its north (and will only receive the $q$ message initiated by the collision), and so will never detach, ensuring that the entire path which may be connected to it through its west side also remains attached.  (See Figures~\ref{fig:new-frame2-full-example-disconnect} and \ref{fig:new-frame2-full-example2-disconnect} for examples.)  Therefore, no assembly containing $\frametiles$ can detach from the assembly if they are not part of an exactly rectangular layer.


%
%
%
%
%
%
%
%
%
%
%

Second, if a path grows from the north side of a $\cgSE$ $c$, around $\alpha$, and arrives with the front of its final tile at the west side of $c$, then it could only have grown as a perfect rectangle.  As previously mentioned, a special collision detection duple will attach to the final tile of the path and the western tile of $c$, and this attachment will initiate the CW propagation of a $d$ message which will exactly follow the path backward to the north side of $c$.  Each tile that the $d$ message passes through will deactivate the $x2'$ glue on its left side, and once that message arrives at the north side of $c$ it will cause $c$ to activate a $p$ glue which will ``prime'' the $\cgSE$ to the inside of it, whose binding will then cause one $x2'$ glue of $c$ as well as the $x2$ glue of the other $x2$-$x2'$ pair of the $\cgSE$ inside it to be deactivated.  This will result in all glues binding that layer to the layer inside of it, other than the $p$ glue, to turn $\off$ (other than one of those on its $\cgSE$, but the glue it was bound to on the inner $\cgSE$ will turn $\off$), causing the layer to be attached with only a single strength-1 glue and therefore to detach.  The detached layer will only at that point have one active $x2$ glue and one active $p$ glue, and therefore nothing can bind to it since all $p'$ glues which have been activated on other layers are hidden by outer layers.  (Additionally, no $q$ message will ever be initiated or received by that layer, and therefore no additional layer will be able to grow on its outside.)  Finally, the remaining frame assembly, without the outer layer, must only have one of the $x2$ glues on its $\cgSE$ $\on$ and therefore no new $\cgSE$ can attach to begin re-growth of another layer.  Only the next priming tile can attach.
\qed
\end{proof} 

replication2.tex
\section{Replication} \label{sec:rep}
In this section, we provide a construction in the STAM which is capable of replicating the shapes of a given set of input assemblies with the restriction that the shapes of the input assembly cannot be disconnected by removing a single tile, i.e. shapes with minimum width (\emph{min-width}) 2.  Furthermore, we show this replication can be done in an exponential manner.
\vspace{-12pt}
\subsection{Exponential, unbounded replication}
We now define what it means for an STAM system to replicate a shape $P$.  In the following definition, we assume that the input assemblies $\sigma_1, \sigma_2, ..., \sigma_n$ all have the same glue on each edge of their perimeter and there is only one of each in the system.  We say that an STAM system $\mathcal{T} = (T, \{\sigma_1, \sigma_2, ..., \sigma_n\}, \tau)$ infinitely replicates the shapes $P_1, P_2, ..., P_n$ provided that 1) $\dom{\sigma_i} = P_i$ for all $i$, 2) there are a bounded number of different terminal assemblies, and 3) there are an infinite number of assemblies of shape $P_i$ for all $i$.  We call assemblies $\sigma_1, \sigma_2, ..., \sigma_n$ replicatable supertiles.  In general, a replicatable supertile in a system $\mathcal{T}$ is a supertile which can be ``replicated''.

In the replication process for a shape $P$, we consider a time step to be the production of a new assembly $\alpha$ with $\dom{\alpha} = P$ for all replicatable supertiles currently in the system.  We say that an STAM system $\mathcal{T}$ \emph{exponentially replicates without bound} the shapes $P_1, P_2, ..., P_n$ provided that 1) the system $\mathcal{T}$ infinitely replicates the shapes $P_1, P_2, ..., P_n$ and 2) if there are $n$ copies of the shape $P_i$ at time step $t$, then there are $2n$ copies of the shape $P_i$ at time step $t+1$.

\begin{theorem}\label{thm:exp_rep}
For any finite set of hole-free, min-width $2$ shapes $P = \{P_1, P_2, ..., P_n\}$, there exists an STAM system $\calT = (T, \sigma_P, 2)$, with $\sigma_P$ a set of $n$ assemblies, one of each shape in $P$, such that $\calT$ exponentially replicates without bound all shapes in $P$.
%
\end{theorem}

We now provide a high level overview of the construction.  Let $P$ be a connected, hole-free, min-width $2$ shape.  Our construction begins with designing a tile set that builds a frame around $\sigma$ where $\dom(\sigma) = P$ which detaches upon completion.  Next, we design tiles so that an inner ring forms within the completed ring.  Once this ring within a ring is complete, it detaches and fills in its interior.  The outer ring is then free to make another copy while the interior of the inner ring can host the growth of another frame.

Our construction begins with adding tiles to our tile set which build a frame around $\sigma$ using the machinery from the previous sections.  We design our tile set for this frame system so that once the frame completes, it detaches from $\sigma$ with (1) exactly one south east corner of the frame which exposes a $z$ glue on the north of the west most tile and a $y$ glue on the west side of the north most tile of that corner, and (2) on every other interior side of the frame, a $y$ glue is exposed.  We refer to this frame as the outer frame.

To construct the set of tiles which forms an inner ring inside the outer frame, we begin by adding to our tile set the tiles shown in Figure~\ref{fig:rep_tiles}.

\begin{figure}[htp]
\centering
  \subfloat[][The tile which begins the growth of the inner frame.]{%
        \label{fig:rep_start_tile-main}%
	        \includegraphics[width=0.75in]{images/rep_start_tile2}
        }%
        \quad\quad
  \subfloat[][A north crawler tile which propagates the $w$ signal north.]{%
        \label{fig:rep_north_crawler-main}%
        		\includegraphics[width=0.75in]{images/rep_north_crawler2}
        }%
        \quad\quad
  \subfloat[][The ``duple'' which allows the $w$ signal to propagate to the east when there is not a $y$ glue for a north crawler tile to cooperatively bind to.]{%
        \label{fig:rep_north_duple-main}%
        		\includegraphics[width=1.5in]{images/rep_north_duple2}
        }%
        \quad\quad
  \subfloat[][The ``filler'' tile.]{%
        \label{fig:rep_filler}%
                \includegraphics[width=0.8in]{images/rep_filler}
        }%
  \caption{The partial tile set which builds an inner frame and fills it.\vspace{-15pt}}
  \label{fig:rep_tiles}
\end{figure}

To complete the tile set for the inner frame, we add rotated versions of each of the tiles discussed so far to $T$ (except for the start tile) so that the $w$ signal may be propagated to the north, east, west, and south of the frame in a counterclockwise fashion.

We now modify the tiles discussed above, so that (1) the inner frame separates from the outer frame, (2) the inner frame fills its interior with tiles and (3) the inner frame exposes $x$ glues along its border like the original shape.  To allow the inner frame to detach, we overlay signals on all of the tiles which turn off all of the $y'$ glues on the inner frame.  We add these signals so that this cascade of signals is triggered once the $w$ signal reaches the start tile.  To ensure we do not have any extra exposed glues after our frame detaches, we add these signals so that they follow the $w$ signal (see Section~\ref{sec:signal-following} for signal following gadgetry).  To fill in the shape, we once again overlay signals on the existing tile set so that when the signal returns to the initial tile, it initiates a signal which exposes strength $2$ \emph{fill} glues allowing for the attachment of ``filler tiles'' on the interior of the inner frame.  These filler tiles simply attach and trigger signals on all $3$ remaining sides which allow for the attachment of more filler tiles.  Next, we add signals to the $y'$ glues on the tiles in the inner frame so that when a $y'$ glue attaches to a $y$ glue on the outer frame, it activates an $x$ glue on the same side.
\vspace{-15pt}
\subsubsection{Frame example}
Figure~\ref{fig:rep_examples-main} shows a schematic diagram of the propagation of the $w$ signal.  Notice that the $w$ signal always attempts to take the counterclockwise most path.  It does this by ``bouncing'' off of glues of existing tiles until it finds an edge which does not have a tile abutting it.
\begin{figure}[htp]
\vspace{-25pt}
\centering
  \subfloat[][]{%
        \label{fig:rep_examples21}%
        \makebox[1.4in][c]{\includegraphics[width=1.5in]{images/rep_examples21}}
        }%
        \quad\quad
  \subfloat[][]{%
        \label{fig:rep_examples22}%
        \makebox[1.4in][c]{\includegraphics[width=1.3in]{images/rep_examples22}}
        }%
  \caption{A schematic view of how the $w$ signal is passed through the inner frame.  The darkly shaded tiles represent the outer frame and the lightly shaded tiles represent the tiles composing the inner frame.  The path through the tiles indicates the flow of the $w$ signals through the inner frame. \vspace{-15pt}}
  \label{fig:rep_examples-main}
\end{figure}

\subsubsection{Exponential, unbounded replication of shapes at scale factor $2$}
Since all shapes at scale factor $2$ are min-width $2$ shapes, Theorem~\ref{thm:exp_rep} yields the following corollary.

\begin{corollary}

For any finite set of hole-free shapes $P = \{P_1, P_2, ..., P_n\}$, let $P' = \{P'_1, P'_2, ..., P'_n\}$ be the shapes of $P$ at scale factor $2$. Then, there exists an STAM system $\calT = (T, \sigma_P', 2)$, with $\sigma_P'$ a set of $n$ assemblies, one of each shape in $P'$, such that $\calT$ exponentially replicates without bound all shapes in $P'$.

%
\end{corollary}

\ifabstract
\later{
\section{Replication} \label{sec:rep_app}

In this section, we provide a construction in the STAM which is capable of replicating the shapes of a given set of input assemblies with the restriction that the shapes of the input assemblies cannot be disconnected by removing a single tile.  We call such shapes min-width $2$ shapes.  Furthermore, we show this replication can be done in an exponential manner.


\subsection{Exponential, unbounded replication}
We now define what it means for an STAM system to replicate a shape $P$.  In the following definition, we assume that the input assemblies $\sigma_1, \sigma_2, ..., \sigma_n$ all have the same glue on each edge of their perimeter and there is only one of each in the system.  We say that an STAM system $\mathcal{T} = (T, \{\sigma_1, \sigma_2, ..., \sigma_n\}, \tau)$ infinitely replicates the shapes $P_1, P_2, ..., P_n$ provided that 1) $\dom{\sigma_i} = P_i$ for all $i$, 2) there are a bounded number of different terminal assemblies, and 3) there are an infinite number of assemblies of shape $P_i$ for all $i$.  We call assemblies $\sigma_1, \sigma_2, ..., \sigma_n$ replicatable supertiles.  In general, a replicatable supertile in a system $\mathcal{T}$ is a supertile which can be ``replicated''.

In the replication process for a shape $P$, we consider a time step to be producing a new assembly $\alpha$ with $\dom{\alpha} = P$ for all replicatable supertiles currently in the system.  We say that an STAM system $\mathcal{T}$ \emph{exponentially replicates without bound} the shapes $P_1, P_2, ..., P_n$ provided that 1) the system $\mathcal{T}$ infinitely replicates the shapes $P_1, P_2, ..., P_n$ and 2) if there are $n$ copies of the shape $P_i$ at time step $t-1$, then there are $2n$ copies of the shape $P_i$ at time step $t$.

We say that a shape $P$ is a min-width $2$ shape provided that two conditions hold: 1) if $\vec{v} = (v_1, v_2) \in \dom{(P)}$, then either $(v_1-1, v_2) \in \dom{(P)}$ or $(v_1+1, v_2) \in \dom{(P)}$ and 2) if $\vec{v} = (v_1, v_2) \in \dom{(P)}$, then either $(v_1, v_2 - 1) \in \dom{(P)}$ or $(v_1, v_2+1) \in \dom{(P)}$.  Intuitively, we can think of this as the set of shapes which cannot be disconnected by removing a single tile.

%

The next theorem states that we can exponentially replicate without bound any hole-free, connected, min-width $2$ shape.  Our proof of this theorem is by construction.  We now provide a high level overview of the construction.  Let $P$ be a connected, hole-free, min-width $2$ shape.  Our construction begins with designing a tile set that builds a frame around $P$ which detaches upon completion.  Next, we design tiles so that an inner ring forms within the completed ring.  Once this ring within a ring is complete, it detaches and fills in its interior.  The outer ring is then free to make another copy while the interior of the inner ring can host the growth of another ring.

\begin{theorem}\label{thm:exp_rep}
There exists an STAM tile set at temperature $2$ which exponentially replicates without bound any set of min-width $2$ shapes $P_1, P_2, ..., P_n$.
\end{theorem}

We now present a proof sketch of Theorem~\ref{thm:exp_rep}.  We show the theorem holds when $n=1$ (that is, there is only one input assembly shape to be replicated), and note that it easily generalizes to $n>1$.   Let $P$ be a hole-free, connected, min-width $2$ shape in $\mathbb{N}^2$ which has component size $2$.  We create a system $\mathcal{T} = (T, \sigma, 2)$ where $T$ is the tile set we describe throughout the construction and $\sigma$ is an assembly with $\dom(\sigma) = P$ whose perimeter tiles all expose a glue $x$.  Our construction begins with adding tiles to $T$ which build a frame around $\sigma$ using the machinery from the previous sections.  We design our tile set for this frame system so that once the frame completes, it detaches from $\sigma$.  Furthermore, we design the tile set of this system, so that 1) there exists exactly one south east corner of the frame which exposes a $z$ glue on the north of the west most tile and a $y$ glue on the west side of the north most tile and 2) on every other interior side of the frame, a $y$ glue is exposed.  An example of such a frame is shown in Figure~\ref{fig:rep_frame_ex}.  We refer to this frame as the outer frame.

\begin{figure}[htp]
\centering
    \includegraphics[width=2.0in]{images/rep_frame_ex2}
    \caption{An example of the glues lining the interior of a frame.}
    \label{fig:rep_frame_ex}
\end{figure}

To construct the set of tiles which forms an inner ring inside the previously constructed ring, we begin by adding to $T$ the tile shown in Figure~\ref{fig:rep_start_tile} which we call the start tile.  Notice that this tile will bind to our specially selected south east corner and propagate a $w$ signal to the north.  Next, we add the tile shown in Figure~\ref{fig:rep_north_crawler} to $T$ which will cooperatively bind to the $y$ glue of the outer frame and the $w$ glue of the tile shown in Figure~\ref{fig:rep_start_tile}.  We call this tile the north crawler tile.  North crawler tiles will continue to attach until 1) there is no longer a $y$ glue to which the north crawler tile can cooperatively bind or 2) the attachment of the north crawler tile is prevented by a tile existing in the outer frame.  In the case of 1, we add the two tiles shown in Figure~\ref{fig:rep_north_duple} to $T$ which we think of as being preformed and binding cooperatively with the propagated $w$ signal and the $y$ glue of the outer frame.  Once this ``duple'' binds, it will start the propagation of a $w$ signal to the east.  In the case of 2, the $y'$ glue on the top of the north crawler tile will ``bounce'' off of the $y$ glue on the outer frame tile which is preventing it from continuing and start propagating the $w$ signal west.

To complete the tile set for the inner frame, we add rotated versions of each of the tiles discussed so far to $T$ (except for the start tile) so that the $w$ signal may be propagated to the north, east, west, and south of the frame in a counterclockwise fashion.

We now modify the tiles discussed above, so that 1) the inner frame separates from the outer frame, 2) the inner frame fills its interior with tiles and 3) the inner frame exposes $x$ glues along its border like the original shape.  To allow the inner frame to detach, we overlay signals on all of the tiles which turn off all of the $y'$ glues on the inner frame.  We add these signals so that this cascade of signals is triggered once the $w$ signal reaches the start tile.  To ensure we do not have any extra exposed glues after our frame detaches, we add these signals so that they follow the $w$ signal as seen in previous sections.  To fill in the shape, we once again overlay signals on the existing tile set so that when the signal returns to the initial tile, the initial tile sends out a signal which exposes strength $2$ glues which allow for the attachment of ``filler tiles''.  These filler tiles simply attach, and trigger signals on all $3$ remaining sides which allow for the attachment of more filler tiles.  Next, we can add extra signals to the $y'$ glues on the tiles in the inner frame so that when the $y'$ glues ``bounces'' off the $y$ glue on the outer frame, it exposes an $x$ glue on the same side of the tile as it is located.

\begin{figure}[htp]
\centering
    \includegraphics[width=1.5in]{images/rep_start_tile2}
    \caption{The tile which begins the growth of the inner frame.}
    \label{fig:rep_start_tile}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=1.5in]{images/rep_north_crawler2}
    \caption{The tile which propagates the $w$ signal to the north.}
    \label{fig:rep_north_crawler}
\end{figure}

\begin{figure}[htp]
\centering
    \includegraphics[width=2.5in]{images/rep_north_duple2}
    \caption{The ``duple'' which allows the $w$ signal to propagate to the east when there is not a $y$ glue for the north crawler tile to cooperatively bind to.}
    \label{fig:rep_north_duple}
\end{figure}

\begin{figure}[htp]
\centering
        \includegraphics[width=1.5in]{images/rep_filler}
        \caption{The ``filler'' tile.}
        \label{fig:rep_filler}
\end{figure}


\subsubsection{Frame example}
Figure~\ref{fig:rep_examples} shows a schematic diagram of the propagation of the $w$ signal.  Notice that the $w$ signal always attempts to take the counterclockwise most path.  It does this by ``bouncing'' off of glues of existing tiles until it finds an edge which does not have a tile abutting it.
\begin{figure}[htp]
\centering
  \subfloat[][]{%
        \label{fig:rep_examples21}%
        \makebox[1.6in][c]{\includegraphics[width=1.5in]{images/rep_examples21}}
        }%
        \quad\quad
  \subfloat[][]{%
        \label{fig:rep_examples22}%
        \makebox[1.6in][c]{\includegraphics[width=1.7in]{images/rep_examples22}}
        }%
  \caption{A schematic view of how the $w$ signal is passed through the inner frame.  The darkly shaded tiles represent the outer frame and the lightly shaded tiles represent the tiles composing the inner frame.  The path through the tiles indicates the flow of the $w$ signals through the inner frame.}
  \label{fig:rep_examples}
\end{figure}

\subsubsection{Proof of correctness}
We now show that the system $\mathcal{T}$ described above exponentially replicates without bound the shape $P$.  To see this, we first argue that the system infinitely replicates the shape $P$, and then we show that the system exponentially replicates $P$ without bound.

It is straight forward to see that the $w$ signal always returns to the start tile, and consequently that the frame detaches and fills in.  Note that this implies that there will be an infinite number of $\alpha$ assemblies in $\mathcal{A}_{\Box}[\mathcal{T}]$ with the property that $\dom{\alpha} = P$.   Thus, we show that after the inner frame detaches from the outer frame, it cannot inadvertently bind to another assembly in the system which will show that there are only a bounded number of terminal assemblies in the system.  To see this, note that the only glues exposed on the outside of the inner frame after it detaches are $w$ and $x$ glues and one $z$ glue.  But, this is not an issue because there are not any assemblies in the system which expose more than one $w'$ glue or $z'$ glue.  Consequently, the $w$ glues cannot allow for the attachment of other assemblies.

To see that this replication occurs in an exponential manner, note that after each inner frame detaches, they expose $x$ glues which will allow another frame to begin to form.  Thus, if at time step $t$ there are $n$ replicatable supertiles, at time step $t$ there will be $2n$ replicatable supertiles.  Consequently, $\mathcal{T}$ exponentially replicates $P$ without bound.

} %
\fi

signal-following.tex
\subsection{Followable Messages}\label{sec:signal-following}

In this section we show how to pass a massage through a sequence of tiles such that after the message has been passed, a second message can be passed through the exact same sequence of tiles in either the same order or the reverse order. For example, in our frame construction, signals propagate an $f$ message through a sequences of layer 1 tiles $\{\T_i\}_{i=0}^n$ (not necessarily distinct). In our construction, we propagate an $f$ message through layer 1 through a series of glue activations such that this message follows the sequence of tiles $\{\T_i\}_{i=0}^n$ in that order. In this case, we say that the $br$ message \emph{follows} the $f$ message \emph{in order}. Here we also show how to \emph{follow} $\{\T_i\}_{i=0}^n$ in reverse order. In this case, we say that the message \emph{follows} the $f$ message \emph{in reverse}. We now give signal tile gadgets to ensure that this can be done.

Figure~\ref{fig:signal-following-none} shows an $f$ message being passed through a tile. Let $F$ denote this tile. This message enters from the south and then may potentially be output through the north, east, or south, depending on which collisions, if any, occur.  The goal is to ensure that a second message can be output through exactly that same side (and no others). Other cases where the $f$ message enters through the north, east, or south are equivalent up to rotation.

\begin{figure}[htp]
\centering
    \includegraphics[width=1.5in]{images/signal-following-none}
    \caption{An example of signals used to propagate an $f$ message CCW.}
  \label{fig:signal-following-none}
\end{figure}

Figure~\ref{fig:signal-following-gadget} shows an enhanced version of the $f$ message depicted in Figure~\ref{fig:signal-following-none} where the tile directly below $F$ is now used to store the various routes that signals may take as the $f$ message is being propagated. Note that when the $f$ message is triggered to be output, exactly one of the glues $fn$, $fs$ or $fe$ (corresponding to the north, south or east edge) is fired, and eventually exactly one of the glues $rn$, $rs$ or $re$ is fired. Moreover, notice that the glue $rn$ that is fired is located on the south edge of the tile directly above $F$, the glue $rs$ that is fired is located on the north edge of the tile directly below $F$, and the glue $re$ that is fired is located on the west edge of the tile directly to the east of $F$.

\begin{figure}[htp]
\centering
        \includegraphics[width=2in]{images/signal-following-gadget}
  \caption{An enhanced version of the $f$ message depicted in Figure~\ref{fig:signal-following-none} that can be ``followed''.}
  \label{fig:signal-following-gadget}
\end{figure}

Figure~\ref{fig:signal-following-forward} shows a $d$ message that is following a previously passed $f$ message. As the $d$ message is passed, the single glue $dn$, $ds$, and $de$ in the $\on$ state determines where the $d$ message is output. If the $d$ message is following the $f$ message in order, then the glues $dn$, $ds$, and $de$ will be the glues $fn$, $fs$, and $fe$ from Figure~\ref{fig:signal-following-gadget}. On the other hand, if the $d$ message is following the $f$ message in reverse, then the glues $dn$, $ds$, and $de$ will be the glues $rn$, $rs$, and $re$ from Figure~\ref{fig:signal-following-gadget}.

\begin{figure}[htp]
\centering
    \includegraphics[width=1.5in]{images/signal-following}
    \caption{A $d$ message that is following a previously passed $f$ message.}
  \label{fig:signal-following-forward}
\end{figure}


biomimicry-with-stam.bbl
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
%
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

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

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

\bibitem{AGKS05g}
Qi~Cheng, Gagan Aggarwal, Michael~H. Goldwasser, Ming-Yang Kao, Robert~T.
  Schweller, and Pablo~Moisset de~Espan\'{e}s, \emph{Complexities for
  generalized models of self-assembly}, SIAM Journal on Computing \textbf{34}
  (2005), 1493--1515.

\bibitem{DDFIRSS07}
Erik~D. Demaine, Martin~L. Demaine, S{\'a}ndor~P. Fekete, Mashhood Ishaque,
  Eynat Rafalin, Robert~T. Schweller, and Diane~L. Souvaine, \emph{Staged
  self-assembly: nanomanufacture of arbitrary shapes with ${O}(1)$ glues},
  Natural Computing \textbf{7} (2008), no.~3, 347--370.

\bibitem{2HAMIU}
Erik~D. Demaine, Matthew~J. Patitz, Trent~A. Rogers, Robert~T. Schweller,
  Scott~M. Summers, and Damien Woods, \emph{The two-handed assembly model is
  not intrinsically universal}, 40th International Colloquium on Automata,
  Languages and Programming, ICALP 2013, Riga, Latvia, July 8-12, 2013, Lecture
  Notes in Computer Science, Springer, 2013.

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

\bibitem{evans2014crystals}
Constantine~Glen Evans, \emph{Crystals that count! physical principles and
  experimental investigations of dna tile self-assembly}, Ph.D. thesis,
  California Institute of Technology, 2014.

\bibitem{Signals3DArxiv}
Tyler Fochtman, Jacob Hendricks, Jennifer~E. Padilla, Matthew~J. Patitz, and
  Trent~A. Rogers, \emph{Signal transmission across tile assemblies: 3{D}
  static tiles simulate active self-assembly by 2{D} signal-passing tiles},
  Tech. Report 1306.5005, Computing Research Repository, 2013.

\bibitem{LaWiRe99}
T.H. LaBean, E.~Winfree, and J.H. Reif, \emph{Experimental progress in
  computation by self-assembly of {DNA} tilings}, {DNA} Based Computers
  \textbf{5} (1999), 123--140.

\bibitem{jCCSA}
James~I. Lathrop, Jack~H. Lutz, Matthew~J. Patitz, and Scott~M. Summers,
  \emph{Computability and complexity in self-assembly}, Theory Comput. Syst.
  \textbf{48} (2011), no.~3, 617--647.

\bibitem{MaoLabReiSee00}
Chengde Mao, Thomas~H. LaBean, John~H. Relf, and Nadrian~C. Seeman,
  \emph{Logical computation using algorithmic self-assembly of {D}{N}{A}
  triple-crossover molecules.}, Nature \textbf{407} (2000), no.~6803, 493--6.

\bibitem{jSignals}
Jennifer~E. Padilla, Matthew~J. Patitz, Robert~T. Schweller, Nadrian~C. Seeman,
  Scott~M. Summers, and Xingsi Zhong, \emph{Asynchronous signal passing for
  tile self-assembly: Fuel efficient computation and efficient assembly of
  shapes}, International Journal of Foundations of Computer Science \textbf{25}
  (2014), no.~4, 459--488.

\bibitem{SingleNegative}
Matthew~J. Patitz, Robert~T. Schweller, and Scott~M. Summers, \emph{Exact
  shapes and turing universality at temperature 1 with a single negative glue},
  Proceedings of the 17th international conference on DNA computing and
  molecular programming (Berlin, Heidelberg), DNA'11, Springer-Verlag, 2011,
  pp.~175--189.

\bibitem{jSADSSF}
Matthew~J. Patitz and Scott~M. Summers, \emph{Self-assembly of discrete
  self-similar fractals}, Natural Computing \textbf{1} (2010), 135--172.

\bibitem{jSADS}
Matthew~J. Patitz and Scott~M. Summers, \emph{Self-assembly of decidable sets},
  Natural Computing \textbf{10} (2011), no.~2, 853--877.

\bibitem{ShapeIdentAlgo}
\bysame, \emph{Identifying shapes using self-assembly.}, Algorithmica
  \textbf{64} (2012), no.~3, 481--510.

\bibitem{RothTriangles}
Paul W.~K Rothemund, Nick Papadakis, and Erik Winfree, \emph{Algorithmic
  self-assembly of dna sierpinski triangles}, PLoS Biol \textbf{2} (2004),
  no.~12, e424.

\bibitem{RotWin00}
Paul W.~K. Rothemund and Erik Winfree, \emph{The program-size complexity of
  self-assembled squares (extended abstract)}, STOC '00: Proceedings of the
  thirty-second annual ACM Symposium on Theory of Computing (Portland, Oregon,
  United States), ACM, 2000, pp.~459--468.

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

\bibitem{SolWin07}
David Soloveichik and Erik Winfree, \emph{Complexity of self-assembled shapes},
  SIAM Journal on Computing \textbf{36} (2007), no.~6, 1544--1569.

\bibitem{Winf98}
Erik Winfree, \emph{Algorithmic self-assembly of {D}{N}{A}}, Ph.D. thesis,
  California Institute of Technology, June 1998.

\end{thebibliography}
