The Computing Power of Self-assembling Tilings on the Whole PlaneFlorent BeckerENS Lyon |
Self-assembly is a common phenomenon in nature, where shape and structure emerge from small entities sticking to each other through local interactions. Numerous authors, especially since Winfree, have built a theory of self-assembly algorithms. This framework is especially useful in nano-technologies, where they can be used to manufacture nano-devices more easily. In particular, it is possible to craft DNA polymers whose interaction correspond to the model of self-assembling tilings, in which we will work. The behaviour of these algorithms is now well-understood when building a finite shape, but not for covering the whole plane with a pattern. It is this question which we tackle here.
Self-assembling tilings are a variant of Wang Tilings, with the addition of a glue function and an associated dynamics.
A self-assembling system consists of a set of W Wang Tiles on a set of colors Σ, together with a glue function g:Σ → ℕ, a temperature T ∈ ℕ, and a seed tile σ ∈ W. There is a transition from a pattern p1 to a pattern p′ = p ⊔ {(x,y) ↦ t} (with t∈ W) if the sum of the values of g on the sides shared between (x,y) and its neighbors in p′ is more than T.
The set of productions is the set of patterns which can be reached from {(0,0) ↦ σ} by a sequence of transitions.
We are interested in having productions which cover the whole plane, thus assembling a Wang Tiling. In order to see a pattern covering the whole plane, it is necessary to look at the limit of a sequence of transitions. This limit is well-defined, since a transition can only add a tile, not change an already present tile. This does not necessarily give a tiling of ℤ2 by W, though, since one could just tile a quarter or the plane, or a line, or a spiral…To remedy to this, we say that a self-assembling system is infallible if for any production p and z ∈ ℤ2, there is a sequence of transition from p to some p′ with z ∈ dom(p′). A complete limit of a self-assembling system is the limit of some sequence of transitions which covers the whole plane. In an infallible system, we are interested in the set of complete limits of the system.
The temperature parameter plays a crucial role. In particular, at temperature 1, the dynamic of self-assembly is that of a greedy tiling algorithm: take a finite pattern, and add any matching tile on its border, even if only one neighbor is known. If one add tiles along a path, there can be no computation, and one gets a periodic pattern.
As it turns out, the set of complete limits of an infallible temperature 1 system is reduced to a unique periodic pattern (modulo some syntactic equivalence on tiles).
At temperature 2 and higher, it is possible to have more control on the assembly, and thus to get more interesting patterns. In particular, we would like to characterize which sets of tilings one can program this way. It is very clear that one can only get recursively enumerable sets, but is it possible to give some complexity bounds. Since Berger and Robinson, it is known that quasi-periodic patterns are crucial for these questions. Thus, we will try to see what quasi-periodic patterns it is possible to get.
The first thing to notice is that it is possible to get a set of strictly quasi-periodic patterns with self-assembly, the set of base patterns of Robinson’s tiling.
We define the complexity of a set of patterns as the complexity of the set of squares which can be extracted from these patterns. The complexity of the set of complete limits of an infallible temperature 2 self-assembling system is then at most NTIME(2f(n)) in the quasi-periodic case, where f(n) is the quasi-periodicity function. The reason is that in order to take the maximum time before assembling a n × n square, at temperature 2, one has to tile a band of width n − 1. Predicting how to tile this band is in NTIME(2n). But in order to get all n × n extracted squares, one needs at worse to assemble an f(n) × f(n) square.
At higher temperatures, the shape one can assemble before getting the first f(n) × f(n) square is a planar graph of tree-width f(n) − 1. The open problem is to estimate the complexity of the tiling problem of such graphs.
This document was translated from LATEX by HEVEA.