by Yuriy Brun

Abstract:

Formalized study of self-assembly has led to the definition of the tile assembly model. 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 $\Theta(1)$ distinct tile types and prove the assembly time is linear in the size of the input.

Citation:

Yuriy Brun, Arithmetic computation in the tile assembly model: Addition and multiplication, Theoretical Computer Science, vol. 378, no. 1, June 2007, pp. 17–31.

Related:

Extended and revised version of "Adding and multiplying in the tile
assembly model" in FNANO 2007.

Bibtex:

@article{Brun07arith, author = {Yuriy Brun}, title = {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun07arith.pdf}{Arithmetic computation in the tile assembly model: {A}ddition and multiplication}}, journal = {Theoretical Computer Science}, venue = {TCS}, volume = {378}, number = {1}, pages = {17--31}, month = {June}, date = {3}, year = {2007}, issn = {0304-3975}, doi = {10.1016/j.tcs.2006.10.025}, publisher = {Elsevier}, address = {Essex, {UK}}, note = {Extended and revised version of~\ref{Brun07fnano}. \href{https://doi.org/10.1016/j.tcs.2006.10.025}{DOI: 10.1016/j.tcs.2006.10.025}}, previous = {Extended and revised version of "Adding and multiplying in the tile assembly model" in FNANO 2007.}, abstract = {Formalized study of self-assembly has led to the definition of the tile assembly model. 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 $\Theta(1)$ distinct tile types and prove the assembly time is linear in the size of the input.}, }