Difference between revisions of "Directed Tile Assembly Systems"
| (5 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | Informally, a directed [[Tile Assembly System (TAS) | TAS]] (a.k.a. deterministic, confluent, produces a unique assembly) is a TAS that can only produce exactly one [[Assembly#Terminal Assembly | terminal assembly]]. In general, even a directed TAS may have a very large | |
| − | |||
| − | |||
| − | Informally, a directed [[Tile Assembly System (TAS) | TAS]] is a TAS that can only produce exactly one [[Assembly#Terminal Assembly | terminal assembly]]. In general, even a directed TAS may have a very large | ||
(perhaps uncountably infinite) number of different assembly | (perhaps uncountably infinite) number of different assembly | ||
sequences leading to its terminal assembly. This seems to make it | sequences leading to its terminal assembly. This seems to make it | ||
| Line 11: | Line 8: | ||
assembly sequence that is locally deterministic, then $\mathcal{T}$ | assembly sequence that is locally deterministic, then $\mathcal{T}$ | ||
is directed. | is directed. | ||
| + | |||
| + | __TOC__ | ||
==Definition== | ==Definition== | ||
| − | Let $\mathcal{T} = (T, \sigma, \tau)$ be a TAS. The set $ | + | 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*} | $\begin{eqnarray*} | ||
| − | \alpha \longrightarrow \alpha' & \ | + | \alpha \longrightarrow \alpha' & \;\text{iff} & \text{there is an assembly sequence } \vec{\alpha} = (\alpha_0,\alpha_1,\ldots) \\& & \text{such that } \alpha_0 = \alpha \text{ and } \alpha' = \text{res}{\vec{\alpha}}.\\ |
\end{eqnarray*}$ | \end{eqnarray*}$ | ||
| − | We say that $\mathcal{T}$ is directed | + | We say that $\mathcal{T}$ is directed if the relation $\longrightarrow$ is directed, i.e., if for all $\alpha,\alpha' \in \mathcal{A}[T]$, there exists $\alpha'' \in \mathcal{A}[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== | ==Local Determinism== | ||
| Line 50: | Line 49: | ||
</bibtex></ref> | </bibtex></ref> | ||
</references> | </references> | ||
| + | |||
| + | [[Category: Terminology]] | ||
| + | [[Category:Self-assembly]] | ||
Latest revision as of 11:40, 18 July 2022
Informally, a directed TAS (a.k.a. deterministic, confluent, produces a unique assembly) 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.
Contents
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' & \;\text{iff} & \text{there is an assembly sequence } \vec{\alpha} = (\alpha_0,\alpha_1,\ldots) \\& & \text{such that } \alpha_0 = \alpha \text{ and } \alpha' = \text{res}{\vec{\alpha}}.\\ \end{eqnarray*}\)
We say that \(\mathcal{T}\) is directed if the relation \(\longrightarrow\) is directed, i.e., if for all \(\alpha,\alpha' \in \mathcal{A}[T]\), there exists \(\alpha'' \in \mathcal{A}[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
