Difference between revisions of "Directed Tile Assembly Systems"

From self-assembly wiki
Jump to navigation Jump to search
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
__TOC__
+
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
−
 
 
−
==Overview==
 
−
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 ${\mathcal{A}[\mathcal{T}]$ is partially ordered by the relation $\longrightarrow$ defined by
+
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' & \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}}.\\
+
\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 (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$.
+
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==
 
Soloveichik and Winfree <ref name=SolWin07 /> have defined a
 
Soloveichik and Winfree <ref name=SolWin07 /> have defined a
−
property, {\it local determinism}, of assembly sequences and proven
+
property, ''local determinism'', of assembly sequences and proven
 
the remarkable fact that, if a TAS $\mathcal{T}$ has ''any''
 
the remarkable fact that, if a TAS $\mathcal{T}$ has ''any''
 
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}$ ``just barely'' binds to the existing assembly (meaning that is does so with a summed strength of bonds equal to exactly $\tau$);
+
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 ``output-neighbors'' (i.e. those adjacent tiles which bound after the tile at $\vec{m}$) are deleted from the ${\it result}$ of
+
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.
Line 51: 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.

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. ↑ 1.0 1.1 David Soloveichik, Erik Winfree - Complexity of Self-Assembled Shapes
    SIAM Journal on Computing 36(6):1544-1569,2007
    Bibtex
    Author : David Soloveichik, Erik Winfree
    Title : Complexity of Self-Assembled Shapes
    In : SIAM Journal on Computing -
    Address :
    Date : 2007
Retrieved from "http://self-assembly.net/wiki/index.php?title=Directed_Tile_Assembly_Systems&oldid=1880"