CaltechAUTHORS
  A Caltech Library Service

Limitations of self-assembly at temperature 1

Doty, David and Patitz, Matthew J. and Summers, Scott M. (2011) Limitations of self-assembly at temperature 1. Theoretical Computer Science, 412 (1-2). pp. 145-158. ISSN 0304-3975. https://resolver.caltech.edu/CaltechAUTHORS:20110301-084205329

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20110301-084205329

Abstract

We prove that if a set X ⊆ Z^2 weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition known as pumpability, then X is a semilinear set. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a deterministic two-dimensional tile assembly system. We employ this result to show that, unlike the case of temperature 2 self-assembly, no discrete self-similar fractal weakly self-assembles at temperature 1 in a pumpable tile assembly system.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1016/j.tcs.2010.08.023DOIUNSPECIFIED
http://www.sciencedirect.com/science/article/B6V1G-50XS6MD-4/2/69ca07be4f932d94419dfb055c4d622dPublisherUNSPECIFIED
Additional Information:© 2010 Elsevier B.V. Available online 3 September 2010. This research was supported in part by National Science Foundation grants 0652569 and 0728806. We wish to thank Maria Axenovich, Matt Cook, and Jack Lutz for useful discussions. We would also like to thank Niall Murphy, Turlough Neary, Damien Woods, and Anthony Seda for inviting us to present a preliminary version of this research at the International Workshop on The Complexity of Simple Programs, University College Cork, Ireland on December 6th and 7th, 2008. Finally, we want to thank the anonymous reviewers who poured great time and effort into their reviews and helped to make this a much better paper. The research of the first author was partially supported by NSF grant CCF:0430807, by Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant R2824A01 to Lila Kari, the Canada Research Chair Award in Biocomputing to Lila Kari, and by the NSF Computing Innovation Fellowship grant. The research of the third author was supported in part by NSF-IGERT Training Project in Computational Molecular Biology Grant number DGE-0504304.
Funders:
Funding AgencyGrant Number
NSFCCF-0430807
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
DiscoveryR2824A01
Canada Research Chair Award UNSPECIFIED
NSF-IGERT Training Project in Computational Molecular BiologyDGE-0504304
NSF Computing Innovation Fellowship UNSPECIFIED
NSF0652569
NSF0728806
Subject Keywords:Tile self-assembly; General-purpose computation; Temperature 1; Semilinear set
Issue or Number:1-2
Record Number:CaltechAUTHORS:20110301-084205329
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20110301-084205329
Official Citation:David Doty, Matthew J. Patitz, Scott M. Summers, Limitations of self-assembly at temperature 1, Theoretical Computer Science, Volume 412, Issues 1-2, Complexity of Simple Programs, 2 January 2011, Pages 145-158, ISSN 0304-3975, DOI: 10.1016/j.tcs.2010.08.023. (http://www.sciencedirect.com/science/article/B6V1G-50XS6MD-4/2/69ca07be4f932d94419dfb055c4d622d)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22563
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:01 Mar 2011 17:11
Last Modified:03 Oct 2019 02:38

Repository Staff Only: item control page