Arithmetic computation in the tile assembly model: Addition and multiplication |
| |
Authors: | Yuriy Brun |
| |
Affiliation: | Department of Computer Science, University of Southern California, Los Angeles, CA 90089-2910, United States |
| |
Abstract: | Formalized study of self-assembly has led to the definition of the tile assembly model Erik Winfree, Algorithmic self-assembly of DNA, Ph.D. Thesis, Caltech, Pasadena, CA, June 1998; Paul Rothemund, Erik Winfree, The program-size complexity of self-assembled squares, in: ACM Symposium on Theory of Computing, STOC02, Montreal, Quebec, Canada, 2001, pp. 459–468]. Research has identified two issues at the heart of self-assembling systems: the number of steps it takes for an assembly to complete, assuming maximum parallelism, and the minimal number of tiles necessary to assemble a shape. In this paper, I define the notion of a tile assembly system that computes a function, and tackle these issues for systems that compute the sum and product of two numbers. I demonstrate constructions of such systems with optimal Θ(1) distinct tile types and prove the assembly time is linear in the size of the input. |
| |
Keywords: | Self-assembly Adder Multiplier Tile assembly model Crystal growth Molecular computation |
本文献已被 ScienceDirect 等数据库收录! |
|