Step-wise tile assembly with a constant number of tile types

作者：Manuch Jan^*; Stacho Ladislav; Stoll Christine

来源：Natural Computing, 2012, 11(3): 535-550.

DOI：10.1007/s11047-012-9321-1

• Stage assembly
• Self-assembly
• Shape
• Tile complexity
• Search number
• Pathwidth
• Caterpillar decomposition

In this paper, we study the step-wise tile assembly model introduced by Reif (in: Based computers III, vol 48 of DIMACS, 1999) in which shape is assembled in multiple steps. In each step the partially built structure is exposed to a new set of tiles. We show that an N x N square can be assembled in N steps using a constant number of tile types. In general, we show that a constant number of tile types (24) is sufficient to assemble a large class of shapes in n steps, where n is the number of tiles of the shape. This class includes all shapes obtained from any shape by scaling by a factor of 2, in which case only 14 tile types suffices. For general shapes, we show that the tile complexity of this model is related to the monotone connected node search number of a spanning tree of the shape assuming the number of steps is n.

• 出版日期2012-9