License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.360
URN: urn:nbn:de:0030-drops-50935
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5093/
Go to the corresponding LIPIcs Volume Portal

Chen, Ho-Lin ; Doty, David ; Manuch, Ján ; Rafiey, Arash ; Stacho, Ladislav

Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems

pdf-format:
10.pdf (0.9 MB)

Abstract

We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap.

This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly and avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2015:5093,
  author =	{Ho-Lin Chen and David Doty and J{\'a}n Manuch and Arash Rafiey and Ladislav Stacho},
  title =	{{Pattern Overlap Implies Runaway Growth in Hierarchical Tile Systems}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{360--373},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5093},
  URN =		{urn:nbn:de:0030-drops-50935},
  doi =		{10.4230/LIPIcs.SOCG.2015.360},
  annote =	{Keywords: self-assembly, hierarchical, pumping}
}

Keywords: self-assembly, hierarchical, pumping
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI