Difference between revisions of "Directed Tile Assembly Systems"
| Line 27: | Line 27: | ||
assembly sequence that is locally deterministic, then $\mathcal{T}$ | assembly sequence that is locally deterministic, then $\mathcal{T}$ | ||
is directed. Intuitively, an assembly sequence $\vec{\alpha}$ is locally deterministic if (1) each | is directed. Intuitively, an assembly sequence $\vec{\alpha}$ is locally deterministic if (1) each | ||
| − | tile added in $\vec{\alpha}$ | + | tile added in $\vec{\alpha}$ "just barely" binds to the existing assembly (meaning that is does so with a summed strength of bonds equal to exactly $\tau$); |
(2) if a tile of type $t_0$ at a location $\vec{m}$ and its | (2) if a tile of type $t_0$ at a location $\vec{m}$ and its | ||
| − | immediate | + | immediate "output-neighbors" (i.e. those adjacent tiles which bound after the tile at $\vec{m}$) are deleted from the [[Assembly#Assembly Sequence | result]] of $\vec{\alpha}$, then no tile of type $t \ne t_0$ can attach itself |
| − | $\vec{\alpha}$, then no tile of type $t \ne t_0$ can attach itself | ||
to the thus-obtained configuration at location $\vec{m}$; and (3) | to the thus-obtained configuration at location $\vec{m}$; and (3) | ||
the result of $\vec{\alpha}$ is terminal. | the result of $\vec{\alpha}$ is terminal. | ||
Revision as of 20:23, 21 May 2013
Overview
Informally, a directed TAS is a TAS that can only produce exactly one terminal assembly. In general, even a directed TAS may have a very large (perhaps uncountably infinite) number of different assembly sequences leading to its terminal assembly. This seems to make it very difficult to prove that a TAS is directed. Fortunately, Soloveichik and Winfree [1] have defined a property, local determinism, of assembly sequences and proven the remarkable fact that, if a TAS \(\mathcal{T}\) has any assembly sequence that is locally deterministic, then \(\mathcal{T}\) is directed.
Definition
Let \(\mathcal{T} = (T, \sigma, \tau)\) be a TAS. The set \({\mathcal{A}[\mathcal{T}]\) is partially ordered by the relation \(\longrightarrow\) defined by
\(\begin{eqnarray*} \alpha \longrightarrow \alpha' & \textmd{iff} & \textmd{there is an assembly sequence } \vec{\alpha} = (\alpha_0,\alpha_1,\ldots) \\& & \textmd{such that } \alpha_0 = \alpha \textmd{ and } \alpha' = \res{\vec{\alpha}}.\\ \end{eqnarray*}\)
We say that \(\mathcal{T}\) is directed (a.k.a. deterministic}, confluent, produces a unique assembly}) if the relation \(\longrightarrow\) is directed, i.e., if for all \(\alpha,\alpha' \in \prodasm{T}\), there exists \(\alpha'' \in \prodasm{T}\) such that \(\alpha \longrightarrow \alpha''\) and \(\alpha' \longrightarrow \alpha''\). It is easy to show that \(\mathcal{T}\) is directed if and only if there is a unique terminal assembly \(\alpha \in \mathcal{A}[\mathcal{T}]\) such that \(\sigma \longrightarrow \alpha\).
Local Determinism
Soloveichik and Winfree [1] have defined a property, local determinism, of assembly sequences and proven the remarkable fact that, if a TAS \(\mathcal{T}\) has any assembly sequence that is locally deterministic, then \(\mathcal{T}\) is directed. Intuitively, an assembly sequence \(\vec{\alpha}\) is locally deterministic if (1) each tile added in \(\vec{\alpha}\) "just barely" binds to the existing assembly (meaning that is does so with a summed strength of bonds equal to exactly \(\tau\)); (2) if a tile of type \(t_0\) at a location \(\vec{m}\) and its immediate "output-neighbors" (i.e. those adjacent tiles which bound after the tile at \(\vec{m}\)) are deleted from the result of \(\vec{\alpha}\), then no tile of type \(t \ne t_0\) can attach itself to the thus-obtained configuration at location \(\vec{m}\); and (3) the result of \(\vec{\alpha}\) is terminal.
References
- ↑ 1.0 1.1
David Soloveichik, Erik Winfree - Complexity of Self-Assembled Shapes
- SIAM Journal on Computing 36(6):1544-1569,2007
- BibtexAuthor : David Soloveichik, Erik Winfree
Title : Complexity of Self-Assembled Shapes
In : SIAM Journal on Computing -
Address :
Date : 2007
