Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability

Autor:	Fekete, Sándor P., Schweller, Robert T., Winslow, Andrew
Rok vydání:	2015
Předmět:	Computer Science - Computational Geometry Computer Science - Emerging Technologies
Druh dokumentu:	Working Paper
Popis:	We introduce a new model of algorithmic tile self-assembly called size-dependent assembly. In previous models, supertiles are stable when the total strength of the bonds between any two halves exceeds some constant temperature. In this model, this constant temperature requirement is replaced by an nondecreasing temperature function $\tau : \mathbb{N} \rightarrow \mathbb{N}$ that depends on the size of the smaller of the two halves. This generalization allows supertiles to become unstable and break apart, and captures the increased forces that large structures may place on the bonds holding them together. We demonstrate the power of this model in two ways. First, we give fixed tile sets that assemble constant-height rectangles and squares of arbitrary input size given an appropriate temperature function. Second, we prove that deciding whether a supertile is stable is coNP-complete. Both results contrast with known results for fixed temperature. Comment: In proceedings of ISAAC 2015
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1509.06898 Zobrazit plný text záznamu View this record from Arxiv