Polyomino Tile Assembly Model (polyTAM)

The Polyomino Tile Assembly Model

Here we present the Polyomino Tile Assembly Model. square tile version. A polyomino is a finite subset of the regular square tiling of the 2D plane with a connected interior. graph version. A polyomino is a subgraph \(P\) of the grid graph such that for any cut of \(P\), there is an edge that crosses the cut. For convenience, we always assume that any polyomino is such that leftmost vertex of the bottommost vertices lies at the origin \((0,0)\). Note that any polyomino can be translated in the plane so that this assumption holds. Then, relative to the vertex of a polyomino \(P\) that lies at the origin, we assign a coordinate pair to each of the vertices of \(P\) and.

In the Polyomino Tile Assembly Model, a \(\emph{polyomino tile type}\) (or simply \(\emph{tile type}\)) is a polyomino, along with an assignment of a \(\emph{glue label}\) -- often represented as a finite string, and a nonnegative integer \(\emph{strength}\) to each edge of the polyomino. A glue~\(g\) that appears on multiple tile types always has the same strength~\(s_g\). There are a finite set \(T\) of tile types, but an infinite number of copies of each tile type, with each copy being referred to as a \(\emph{polyomino tile}\) (or simply \(\emph{tile}\)).

A partial function \(f:\Z^2 \dashrightarrow T \times \Z^2\) is said to be \(\emph{consistent}\) with \(T\) if the following holds.

If \(f(\vec{v}) = (P,\vec{0}\, )\) and \(P\) has a vertex at \(\vec{t}\), then \(f(\vec{v} + \vec{t}) = (P, \vec{t}\, )\).

An \(\emph{assembly}\) is a positioning of polyomino tiles on the integer lattice \(\Z^2\), described formally as a partial function \(\alpha:\Z^2 \dashrightarrow T\). Let \(\mathcal{A}^T\) denote the set of all assemblies of tiles from \(T\), and let \(\mathcal{A}^T_{< \infty}\) denote the set of finite assemblies of tiles from \(T\). We write \(\alpha \sqsubseteq \beta\) to denote that \(\alpha\) is a \(\emph{subassembly}\) of \(\beta\), which means that \(\dom\alpha \subseteq \dom\beta\) and \(\alpha(p)=\beta(p)\) for all points \(p\in\dom\alpha\). Two adjacent tiles in an assembly \(\emph{interact}\), or are \(\emph{attached}\), if the glue labels on their abutting sides are equal and have positive strength. Each assembly induces a \(\emph{binding graph}\), a grid graph whose vertices are tiles, with an edge between two tiles if they interact. The assembly is \(\emph{tau-stable}\) if every cut of its binding graph has strength at least \(\tau\), where the strength of a cut is the sum of all of the individual glue strengths in the cut. When \(\tau\) is clear from context, we simply say that a \(\tau\)-stable assembly is stable.

The \(\emph{frontier} \partial\alpha \subseteq \Z^2 \setminus \dom\alpha\) of \(\alpha\) is the set of empty locations adjacent to \(\alpha\) at which a single tile could bind stably.

A \(\emph{tile assembly system}\) (TAS) is a triple \(\calT = (T,\sigma,\tau)\), where \(T\) is a finite set of tile types, \(\sigma:\Z^2 \dashrightarrow T\) is a finite, \(\tau\)-stable \(\emph{seed assembly}\), and \(\tau\) is the \(\emph{temperature}\). An assembly \(\alpha\) is \(\emph{producible}\) if either \(\alpha = \sigma\) or if \(\beta\) is a producible assembly and \(\alpha\) can be obtained from \(\beta\) by the stable binding of a single tile. In this case we write \(\beta\to_1^\calT \alpha\) (to mean~\(\alpha\) is producible from \(\beta\) by the attachment of one tile), and we write \(\beta\to^\calT \alpha\) if \(\beta \to_1^{\calT*} \alpha\) (to mean \(\alpha\) is producible from \(\beta\) by the attachment of zero or more tiles). When \(\calT\) is clear from context, we may write \(\to_1\) and \(\to\) instead. We let \(\prodasm{\calT}\) denote the set of producible assemblies of \(\calT\). An assembly is \(\emph{terminal}\) if no tile can be \(\tau\)-stably attached to it. We let \(\termasm{calT} \subseteq \prodasm{\calT}\) denote the set of producible, terminal assemblies of \(\calT\). A TAS \(\calT\) is \(\emph{directed}\) if \(|\termasm{\calT}| = 1\). Hence, although a directed system may be nondeterministic in terms of the order of tile placements, it is deterministic in the sense that exactly one terminal assembly is producible (this is analogous to the notion of \({\em confluence}\) in rewriting systems).

In this section we define the Polyomino Tile Assembly Model (polyTAM) and relevant terminology.

A \(\emph{polyomino}\) is a plane geometric figure formed by joining one or more equal unit squares edge to edge; it can also be considered a finite subset of the regular square tiling with a connected interior. For convenience, we will assume that each unit square is centered on a point in \(Z^2\). We define the set of \(\emph{edges}\) of a polyomino to be the set of faces from the constituent unit squares of the polyomino that lie on the boundary of the polyomino shape. A \(\emph{polyomino tile}\) is a polyomino with a subset of its edges labeled from some \({\em glue}\) alphabet \(\Sigma\), with each glue having an integer \(\emph{strength}\) value. Two tiles are said to \(\emph{bind}\) when they are placed so that they have non-overlapping interiors and adjacent edges with matching glues; each matching glue binds with force equal to its strength value. An \(\emph{assembly}\) is any connected set of polyominoes whose interiors do not overlap. Given a positive integer \(\tau \in \mathbb{N}\), an assembly is said to be \(\emph{tau-stable}\) or (just \(\emph{stable}\) if \(\tau\) is clear from context), if any partition of the assembly into two non-empty groups (without cutting individual polyominoes) must separate bound glues whose strengths sum to \(\ge \tau\).

The \(\emph{bounding rectangle}\) \(B\) around a polyomino \(P\) is the rectangle with minimal area (and corners lying in \(\mathbb{Z}^2\)) that contains \(P\). For each polyomino shape, we designate one pixel (i.e. one of the squares making up \(P\)) \(p\) as a distinguished pixel that we use as a reference point. More formally, a \(\emph{pixel}\) \(p\) in a polyomino \(P\) (or polyomino tile) is defined in the following manner. Place \(P\) in the plane so that the southwest corner of the bounding rectangle of \(P\) lies at the origin. Then a pixel \(p=(p_1,p_2) \in P\) is a point in \(\mathbb{Z}^2\) which is occupied by a unit square composing the polyomino \(P\). We say that a pixel \(p' \in P\) lies on the perimeter of the bounding rectangle \(B\) if an edge of the pixel \(p'\) lies on an edge of \(B\).

A \(\emph{tile assembly system}\) (TAS) is an ordered triple \(\calT = (T,\sigma,\tau)\) (where \(T\) is a set of polyomino tiles, and \(\sigma\) is a \(\tau\)-stable assembly called the \(\emph{seed}\)) that consists of integer translations of elements of \(T\). \(\tau\) is the \(\emph{temperature}\) of the system, specifying the minimum binding strength necessary for a tile to attach to an assembly. Throughout this paper, the temperature of all systems is assumed to be 1, and we therefore frequently omit the temperature from the definition of a system (i.e. \(\calT = (T,\sigma)\)).

If the tiles in \(T\) all have the same polyomino shape, \(\calT\) is said to be a \(\emph{single-shape}\) system; more generally \(\calT\) is said to be a \(c\)-shape system if there are \(c\) distinct shapes in \(T\). If not stated otherwise, systems described in this paper should by default be assumed to be single-shape systems. If \(T\) consists of unit-square tiles, \(\calT\) is said to be a \(\emph{monomino}\) system.

Given a tile-assembly system \(\calT = (T,\sigma,\tau)\), we now define the set of \(\emph{producible}\) assemblies \(\prodasm{T}\) that can be derived from \(\calT\), as well as the \(\emph{terminal}\) assemblies, \(\termasm{T}\), which are the producible assemblies to which no additional tiles can attach. The assembly process begins from \(\sigma\) and proceeds by single steps in which any single copy of some tile \(t \in T\) may be attached to the current assembly \(A\), provided that it can be translated so that its placement does not overlap any previously placed tiles and it binds with strength \(\ge \tau\). For a system \(\calT\) and assembly \(A\), if such a \(t\in T\) exists, we say \(A \rightarrow^\calT_1 A'\) (i.e. \(A\) grows to \(A'\) via a single tile attachment). We use the notation

A \(\rightarrow^\calT A''\), when \(A\) grows into \(A''\) via 0 or more steps. Assembly proceeds asynchronously and nondeterministically, attaching one tile at a time, until no further tiles can attach. An assembly sequence in a TAS \(\mathcal{T}\) is a (finite or infinite) sequence \(\vec{\alpha} = (\alpha_0 = \sigma,\alpha_1,\alpha_2,\ldots)\) of assemblies in which each \(\alpha_{i+1}\) is obtained from \(\alpha_i\) by the addition of a single tile. An \(\emph{assembly sequence}\) for \(\calT\) is any sequence of stable assemblies \(\langle \sigma=A_1 , \ldots , A_k \rangle\) such that \(A_i \rightarrow^1_\calT A_{i+1}\). The set of producible assemblies \(\prodasm{T}\) is defined to be the set of all assemblies \(A\) such that there exists an assembly sequence for \(\calT\) ending with \(A\) (possibly in the limit). The set of \(\emph{terminal}\) assemblies \(\termasm{T} \subseteq \prodasm{T}\) is the set of producible assemblies such that for all \(A \in \termasm{T}\) there exists no assembly \(B \in \prodasm{T}\) in which \(A\rightarrow^\calT_1 B\). A system \(\calT\) is said to be directed if \(|\termasm{T}|=1\), i.e., if it has exactly one terminal assembly.

Note that the aTAM is simply a specific case of the polyTAM in which all tiles are monominoes, i.e., single unit squares.