Limitations of self-assembly at temperature 1 (Q616501)

A tile system is said to be pumpable if every sufficiently long path of tiles in an assembly of this system contains a segment in which the same tile type repeats, and that furthermore, the subpath between these two occurrences can be repeated indefinitely (pumped) along the same direction as the first occurrence of the segment, without colliding with a previous portion of the path. A linear set \(X\subseteq \mathbb{Z}^{2}\) is a set of integer lattice points with the property that there are three vectors \(\vec{b}, \vec{u}\), and \(\vec{v}\), such that \(X=\{\vec{b}+n\vec{u}+m\vec{v}\mid n,m\in \mathbb{N}\}\); a set is semilinear if it is a finite union of linear sets. In this paper it is shown that if a set \(X\subseteq \mathbb{Z}^{2}\) weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assemble system satisfying the pumpability condition, then \(X\) is a semilinear set. Conversely, every semilinear set weakly self-assembles at temperature 1. This justifies the suggestion that semilinear sets are computationally very simple, based on their relationship to regular languages. Also, an application of this theorem shows that, unlike the case of temperature 2, no non-trivial discrete self-similar fractal -- such as the discrete Sierpinski triangle -- weakly self-assembles at temperature 1 in a directed, pumpable tile assembly system. Finally, some open questions are discussed.