Computability and Complexity in Self-assembly |
| |
Authors: | James I. Lathrop Jack H. Lutz Matthew J. Patitz Scott M. Summers |
| |
Affiliation: | (1) Department of Computer Science, University of Texas–Pan American, Edinburg, TX 78539, USA;(2) Department of Computer Science and Software Engineering, University of Wisconsin–Platteville, Platteville, WI 53818, USA |
| |
Abstract: | This paper explores the impact of geometry on computability and complexity in Winfree’s model of nanoscale self-assembly. We work in the two-dimensional tile assembly model, i.e., in the discrete Euclidean plane ℤ×ℤ. Our first main theorem says that there is a roughly quadratic function f such that a set A⊆ℤ+ is computably enumerable if and only if the set X A ={(f(n),0)∣n∈A}—a simple representation of A as a set of points on the x-axis—self-assembles in Winfree’s sense. In contrast, our second main theorem says that there are decidable sets D⊆ℤ×ℤ that do not self-assemble in Winfree’s sense. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|