Pattern overlap implies runaway growth in hierarchical tile systems

DOI10.20382/JOCG.V7I2A2zbMATH Open1405.68117arXiv1411.6672OpenAlexW3023554497MaRDI QIDQ2970463FDOQ2970463

Authors: David Doty, Ho-Lin Chen, Ján Maňuch, Arash Rafiey, Ladislav Stacho 

Publication date: 30 March 2017

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.

Full work available at URL: https://arxiv.org/abs/1411.6672

Recommendations

• Pattern overlap implies runaway growth in hierarchical tile systems
• Producibility in hierarchical self-assembly
• Producibility in hierarchical self-assembly
• Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals
• Parallelism and time in hierarchical self-assembly

Mathematics Subject Classification ID

Cited In (6)

• Tile automaton in the well-mixed medium
• Pattern overlap implies runaway growth in hierarchical tile systems
• Resiliency to multiple nucleation in temperature-1 self-assembly
• A brief tour of theoretical tile self-assembly
• Producibility in hierarchical self-assembly
• Parallelism and time in hierarchical self-assembly

This page was built for publication: Pattern overlap implies runaway growth in hierarchical tile systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970463)