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

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  ×  N square can be assembled...

Full description

Saved in:
Bibliographic Details
Published in:Natural computing 2012-09, Vol.11 (3), p.535-550
Main Authors: Maňuch, Ján, Stacho, Ladislav, Stoll, Christine
Format: Article
Language:English
Subjects:
Artificial Intelligence
Assembly
Complex Systems
Complexity
Computation
Computer engineering
Computer Science
Computer simulation
Evolutionary Biology
Exposure
Graph theory
Mathematical models
Molecular biology
Processor Architectures
Searching
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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  ×  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 .
ISSN:1567-7818
1572-9796
DOI:10.1007/s11047-012-9321-1