Limitations of Self-Assembly at Temperature 1

Simple item page
dc.creatorDoty, David
dc.creatorPatitz, Matthew J
dc.creatorSummers, Scott M
dc.date2009-03-10
dc.date.accessioned2026-07-07T12:51:33Z
dc.date.available2026-07-07T12:51:33Z
dc.descriptionWe prove that if a set $X \subseteq \Z^2$ weakly self-assembles at temperature 1 in a deterministic tile assembly system satisfying a natural condition known as \emph{pumpability}, then $X$ is a finite union of semi-doubly periodic sets. 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 tile assembly system. Finally, we show that general-purpose computation \emph{is} possible at temperature 1 if negative glue strengths are allowed in the tile assembly model.
dc.description10 page conference submission with additional technical appendix containing proofs
dc.identifierhttps://arxiv.org/abs/0903.1857
dc.identifierhttp://arxiv.org/abs/0903.1857
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/223024
dc.subjectDiscrete Mathematics
dc.titleLimitations of Self-Assembly at Temperature 1
dc.typetext

Files

Collections

arXiv