Abstract Slat Assembly Model (aSAM)
Contents
The abstract Slat Assembly Model (aSAM) is essentially a restricted version of the Polyomino Tile Assembly Model (polyTAM) \cite{Polyominoes}. The polyTAM itself is a generalization of the aTAM \cite{Winf98} in which, rather than square tiles, the basic components are polyominoes (which are shapes composed of unit squares attached along their edges). (Note that we take much of our notation, slightly adapted, from aTAM definitions such as \cite{jSSADST}.) The polyTAM was defined for two-dimensional polyominoes, but the aSAM utilizes three-dimensional polyominoes whose shapes are restricted to be linear arrangements of unit cubes. The basic components of the aSAM are called slats and each is a \(1 \times 1 \times n\) polyomino composed of \(n\) unit cubes, for some \(n \in \mathbb{N}\). Each unit cube of a slat has \(4\) or \(5\) exposed faces, \(5\) if it is on one of the two ends of the slat (in the dimension of length \(n\)), and \(4\) otherwise (i.e. it is an interior cube). On each exposed face of a unit cube may be a \emph{glue}, and each glue is an ordered pair \((l,s)\) where \(l\) is a string and serves as the glue's label and \(s \in \mathbb{Z}^+\) is its strength. An exposed face may also have no glue (which may also be referred to as the null glue). The character `\(*\)' is considered a special character in glue labels and any label may have at most a single `\(*\)' character, which must appear as its rightmost. Given a glue \(g = (l,s)\), if the label \(l\) does not end with the character `\(*\)', then we say the label \(l' = l^*\) (i.e. the string \(l\) concatenated with `\(*\)') represents the complement of \(l\). If \(l\) does end with `\(*\)', then its complement is represented by the string \(l\) truncated by one character to remove the `\(*\)'. Thus a pair of labels are complementary to each other if they consist of the same string up to exactly one of them terminating in `\(*\)', e.g. `\(foo\)' and `\(foo^*\)' are complementary labels. Any two glues which have complementary labels must have the same strength value. If two slats are placed so that faces containing complementary glues are aligned and adjacent to each other, those glues bind with strength equal to the common strength value of those two glues.
A slat type is defined by its length \(n\) and the set of glues on its constituent cubes. For convenience, each slat type is assigned a canonical placement and orientation in \(\mathbb{Z}^3\), with the default being that it has one cube at \((0,0,0)\) and it extends along the \(x\)-axis to \((n-1,0,0)\), and the cubes have designated \(N,E,S,W,U,D\) (i.e. north, east, south, west, up, down) sides which face in the \(+y,+x,-y,-x,+z,-z\) directions, respectively (in the canonical placement). Additionally for convenience, the cubes are numbered from \(0\) to \(n-1\) starting from the cube at \((0,0,0)\) and proceeding in order along the \(x\)-axis (of the slat type in its canonical placement), and for a slat type \(t\) the \(i\)th cube is denoted by \(t[i]\). A slat is an instance of a slat type, and may be in any rotation or orientation in the \(\mathbb{Z}^3\) lattice. A slat is defined by (1) its type \(t\), (2) its translation, which is identified by the coordinates of its \(t[0]\), (3) its direction, taken from the set \(\{-x,+x,-y,+y,-z,+z\}\) where the letter denotes which axis the length-\(n\) dimension is parallel to and \(+\) or \(-\) denotes whether the coordinates of block \(t[n-1]\) are more positive or more negative in that dimension than \(t[0]\), respectively, and (4) its `up' direction which is the side of the cubes pointing in the \(+z\) direction in the slat's current orientation. See \Cref{fig:3D_slat,fig:3D_slat_rotated} for an example of a slat type in canonical placement and a rotated version.
An \emph{assembly} over a slat type set \(S\) consists of placements of slats of types from \(S\) in \(\mathbb{Z}^3\) such that no blocks of any two slats overlap. Given an assembly \(\alpha\), if two slats \(t_1\) and \(t_2\) are placed in \(\alpha\) such that for some block of \(t_1\), say \(t_1[i]\), and some block of \(t_2\), say \(t_2[j]\), a face of \(t_1[i]\) is adjacent to a face of \(t_2[j]\) (irrespective of the directions of \(t_i\) and \(t_j\)) and the glues of those faces are complementary, then they form a bond with the common strength value of those glues. If there is no cut in \(\mathbb{Z}^3\) separating the slats of an assembly into two separate components without cutting bonds whose strengths sum to at least some value \(\tau\), then we say the assembly is \(\tau\)-stable. Given an assembly \(\alpha\), a value \(\tau \in \mathbb{Z}^+\), and a set of slat types \(T\), any set \(S\) of \(i\) surfaces on blocks of the slats composing \(\alpha\), where \(0 < i \le \tau\), such that a slat of some type \(t \in T\) can be positioned in \(\mathbb{Z}^3\) (1) without any of its blocks overlapping any blocks of slats in \(\alpha\) and (2) its glues form bonds of strength summing to \(\ge \tau\) with the glues on the surfaces of \(S\), we call \(S\) a \(T_\tau\)-frontier location of \(\alpha\). Essentially, a \(T_\tau\)-frontier location of assembly \(\alpha\) is a location to which a slat of some type in the set \(T\) can validly attach with at least strength \(\tau\). When \(T\) and \(\tau\) are clear from context we will simply refer to such locations as frontier locations.
A slat assembly system, or SAS, is an ordered triple \((S,\sigma,\tau)\) where \(S\) is a set of slat types, \(\sigma\) is an assembly referred to as the seed assembly, and \(\tau\) is the minimum binding threshold (often referred to as the temperature in the aTAM and the cooperativity in the aSAM). Given a SAS \(\mathcal{S} = (S,\sigma,\tau)\), it is assumed that there are an infinite number of slats of each type from \(T\) available for attachment, and assembly begins from the seed assembly \(\sigma\). Assembly proceeds in discrete steps, with each step consisting of the nondeterministic selection of a frontier location \(f\) for the current assembly \(\alpha\), then the nondeterministic selection of a slat type \(t \in T\) that can bind in \(f\) (in case there are more than one), and then the attachment of a slat of type \(t\) to \(\alpha\), translated and rotated appropriately to bind to \(\alpha\) using the glues of \(f\). Note that the aSAM does not require that there be a path through which the slat of type \(t\) must be able to move in \(\mathbb{Z}^3\) from arbitrarily far from \(\alpha\) into that location without encountering overlaps along the way (i.e. it can be considered to just ``appear in the correct location).\footnote{This aspect of the model is similar to that of other abstract models such as the aTAM, and is meant to make the model computationally tractable at the possible expense of reduced physical realism.} Given an assembly \(\alpha\) in \(\mathcal{S}\), if \(\beta\) can result from \(\alpha\) in a single such step, we say that \(\alpha\) produces \(\beta\) in one step and denote it as \(\alpha \rightarrow^\mathcal{S}_1 \beta\).
We use \(\mathcal{A}^S\) to denote the set of all assemblies of slats over slat type set \(S\). Given a SAS \(\mathcal{S}=(S, \sigma, \tau)\), a sequence of \(k\in\mathbb{Z}^+ \cup \{\infty\}\) assemblies \(\alpha_0, \alpha_1, \ldots\) over \(\mathcal{A}^S\) is called a \(\mathcal{S}\)-assembly sequence if \(\alpha_0 = \sigma\) and, for all \(1\le i < k\), \(\alpha_{i-1} \to^{\mathcal{S}}_1 \alpha_i\). The result of an assembly sequence is the unique limiting assembly of the sequence. For finite assembly sequences, this is the final assembly; whereas for infinite assembly sequences, this is the assembly consisting of all slats from any assembly in the sequence. We say that \emph{\(\alpha\) \(\mathcal{S}\)-produces \(\beta\)} (denoted \(\alpha\to^{\mathcal{S}} \beta\)) if there is a \(\mathcal{S}\)-assembly sequence starting with \(\alpha\) whose result is \(\beta\). We say \(\alpha\) is \(\mathcal{S}\)-producible if \(\sigma\to^{\mathcal{S}}\alpha\) and write \(\mathcal{A}[\mathcal{S}]\) to denote the set of \(\mathcal{S}\)-producible assemblies. We say \(\alpha\) is \emph{\(\mathcal{S}\)-terminal} if \(\alpha\) is \(\tau\)-stable and there exists no assembly which is \(\mathcal{S}\)-producible from \(\alpha\). We denote the set of \(\mathcal{S}\)-producible and \(\mathcal{S}\)-terminal assemblies by \(\mathcal{A}_{\Box}[\mathcal{S}]\). When \(\mathcal{S}\) is clear from context, we may omit \(\mathcal{S}\) from this notation. If there is only a single terminal assembly of \(\mathcal{S}\), i.e. \(|\mathcal{A}_{\Box}[\mathcal{S}]| = 1\), then we say that \(\mathcal{S}\) is directed. Otherwise, it is undirected. Note that a SAS \(\mathcal{S}\) may have multiple (even infinitely many) distinct valid assembly sequences but yet \(\mathcal{S}\) may be directed.
aSAM\(^-\): A restricted version of the aSAM
The aSAM is defined to be a relatively general model for the assembly of slat-based structures. However, the previous experimental work of \cite{ShihNucleation,Shih-OrigamiSlats} and the abstract designs and simulation results of this paper all pertain to a restricted subset of the aSAM that we'll refer to as the Restricted aSAM and denote as the aSAM\(^-\).
The aSAM\(^-\) utilizes the following restrictions:
- All blocks of all slats contained in an assembly are restricted to the two planes \(z=0\) and \(z=1\).
- All slats which attach in the vertical orientation (i.e. their longest dimension is parallel to the \(y\)-axis) do so in the plane \(z=0\).
- All slats which attach in the horizontal orientation (i.e. their longest dimension is parallel to the \(x\)-axis) do so in the plane \(z=1\).
- No slats attach in an orientation such that their longest dimension is parallel to the \(z\)-axis.
- For a given slat type \(t\), all slats of type \(t\) which attach to an assembly will do so in the same orientation. Slat types whose slats always bind in a vertical orientation are referred to as \emph{vertical slats}, and those in horizontal orientation as horizontal slats.
- All glues of a polyomino are on a single side, \(U\) for vertical slats and \(D\) for horizontal slats.
- All glues have strength \(= 1\).
Essentially, the aSAM\(^-\) requires that all slats remain in one of two planes, with the horizontal slats all being on the top plane and the vertical slats all being on the bottom, with the only glues being strength-1 glues between vertical and horizontal slats (i.e. no horizontal slat can bind to another horizontal slat, and no vertical to another vertical). Some examples can be seen in \Cref{fig:tile-a-to-slatts,fig:slat-ribbon-coop8-dup2}.
Simulation of the aTAM by the aSAM
It has been shown that arbitrary abstract Tile Assembly Model (aTAM) systems can be intrinsically simulated by aSAM systems (and in fact, aSAM\(^-\) systems). (See Intrinsic Universality of the aTAM for an overview of intrinsic universality.) For each aTAM system \(\mathcal{T} = (T,\sigma,2)\) there exists an aSAM system \(\mathcal{S} = (S,\sigma',c)\) (for any even value of \(c \ge 2\)) such that \(\mathcal{S}\) simulates \(\mathcal{T}\) in such a way that space is logically divided into square regions, called macrotiles, into which sets of slats bind until a ``representation function \(R\) maps a macrotile to a tile of \(T\).
Since the slats of aSAM systems can, in theory, be arbitrarily long, and the temperature of a system (a.k.a. the cooperativity) can be arbitrarily large, some important metrics of systems performing intrinsic simulation are the maximum length of slats and the size of macrotiles. Therefore, in order to minimize these values, a series of results has shown how different classes of aTAM systems, with increasingly complex dynamics, can be simulated by aSAM systems with the trade-off for the greater dynamics being increasingly longer slats (of maximum length) and increasingly larger macrotiles. The simplest class of systems simulated, with the smallest scale factor and shortest slats, is Zig-Zag_Systems. The next is standard aTAM systems (which don't use across-the-gap cooperation, don't have any glue mismatches in producible assemblies, and are directed), and then there is a simulated class for the removal of each of those constraints. The following table gives an overview of the results.
| aTAM class | Macrotile size | Greatest num slats | Greatest slat length |
|---|---|---|---|
| Zig-zag | \(2c \times 2c\) | \(4c\) | \(3c\) |
| Standard | \(3c \times 3c\) | \(8c\) | \(3c\) |
| Standard plus across-the-gap | \(3c \times 3c\) | \(8c\) | \(4c\) |
| Deterministic with mismatches | \(4c \times 4c\) | \(10c\) | \(4c\) |
| Nondeterministic (full aTAM) | \(5c \times 5c\) | \(13c\) | \(5c\) |
Software and examples
Software for generating aTAM systems for several of these classes, converting classes of aTAM systems to aSAM systems, simulating their self-assembly, and visualizing the results can be found here:
Software Simulators for the aSAM
SlatTAS is a Python-based, graphical simulator for the aSAM. It includes source code, and it supports simulation of the aSAM as well as the kinetic Slat Assembly Model (kSAM).(The latest version can be found at the bottom of the list of packages.)
RodSim is a *much* faster simulator for the aSAM and kSAM written in C++. It does not have any user interface and is completely run from the command line. However, the assemblies that it outputs can be opened and viewed in SlatTAS. (The latest version can be found at the bottom of the list of packages.)
