Arithmetic computation in the tile assembly model: Addition and multiplication
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~\cite{}{Brun07fnano}.
  \href{http://dx.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.},
}