Two lower bounds for self-assemblies at temperature 1

摘要

Self-assembly is an autonomous process by which small simple parts assemble into larger and more complex objects. Self-assembly occurs in nature, for example, when atoms combine to form molecules, and molecules combine to form crystals. It has been suggested that intricate self-assembly schemes will ultimately be useful for circuit fabrication, nanorobotics, DNA computing, and amorphous computing [2, 7]. To study the process of self-assembly we use the Tile Assembly Model proposed by Rothemund and Winfree [5]. This model considers the assembly of square blocks called "tiles" and a set of glues called "binding domains". Each binding domain has a strength. Each of the four sides of a tile can have a glue on it that determines interactions with neighbouring tiles. The two neighbouring tiles form a bond if the binding domains on the touching sides are the same. The strength of this bond is the strength of the matching binding domain. The process of self-assembly is initiated by a single seed tile and proceeds by attaching tiles one by one. A tile can only attach to the growing complex if it binds strongly enough, i.e., if the sum of the strengths of its bonds to the existing complex is at least the temperature τ. It is assumed that there is an infinite supply of tiles of each tile type. When this growing process stops, i.e., no tile can be attached to the existing complex, we say that the tile system has assembled this shape. A tile system is specified by the seed tile, the set of tile types, the strengths of glues and the temperature.