Difference between revisions of "Building n by n squares"

From self-assembly wiki
Jump to navigation Jump to search
(Building $n \times n$ squares)
(Building $n \times n$ squares)
Line 2: Line 2:
 
==Building $n \times n$ squares==
 
==Building $n \times n$ squares==
 
Since Winfree showed in his thesis <ref name=Winf98 /> that the aTAM is computationally universal, we know that we can algorithmically direct the growth of assemblies.  This ability allows for not only the creation of complicated and precise shapes, but also often for them to be created very tile type efficiently (i.e. they require small tile sets - those with few numbers of unique tile types).  A benchmark problem for tile-based self-assembly is that of assembling an $n \times n$ square since this requires that the tiles somehow compute the value of $n$ and thus "know when to stop" at the boundaries.  In <ref name =RotWin00> Rothemund and Winfree showed that binary counters can be used to guide the growth of squares and that thereby it is possible to self-assemble an $n \times n$ square using $O(\log n)$ tile types.
 
Since Winfree showed in his thesis <ref name=Winf98 /> that the aTAM is computationally universal, we know that we can algorithmically direct the growth of assemblies.  This ability allows for not only the creation of complicated and precise shapes, but also often for them to be created very tile type efficiently (i.e. they require small tile sets - those with few numbers of unique tile types).  A benchmark problem for tile-based self-assembly is that of assembling an $n \times n$ square since this requires that the tiles somehow compute the value of $n$ and thus "know when to stop" at the boundaries.  In <ref name =RotWin00> Rothemund and Winfree showed that binary counters can be used to guide the growth of squares and that thereby it is possible to self-assemble an $n \times n$ square using $O(\log n)$ tile types.
 
 
==References==
 
<references>
 
 
<ref name =Winf98><bibtex>
 
@phdthesis{Winf98,
 
  author = "Erik Winfree",
 
  title = "Algorithmic Self-Assembly of DNA",
 
  school = "California Institute of Technology",
 
  year = "1998",
 
  month = "June",
 
}
 
</bibtex></ref>
 
 
<ref name =RotWin00><bibtex>
 
@inproceedings{RotWin00,
 
author = {Paul W. K. Rothemund and Erik Winfree},
 
title = {The Program-size Complexity of Self-Assembled Squares (extended abstract)},
 
booktitle = {STOC '00: Proceedings of the thirty-second annual ACM Symposium on Theory of Computing},
 
year = {2000},
 
isbn = {1-58113-184-4},
 
pages = {459--468},
 
address = {Portland, Oregon, United States},
 
doi = {http://doi.acm.org/10.1145/335305.335358},
 
publisher = {ACM}
 
}
 
</bibtex></ref>
 
 
<ref name =RotWin00><bibtex>
 
@inproceedings{RotWin00,
 
author = {Paul W. K. Rothemund and Erik Winfree},
 
title = {The Program-size Complexity of Self-Assembled Squares (extended abstract)},
 
booktitle = {STOC '00: Proceedings of the thirty-second annual ACM Symposium on Theory of Computing},
 
year = {2000},
 
isbn = {1-58113-184-4},
 
pages = {459--468},
 
address = {Portland, Oregon, United States},
 
doi = {http://doi.acm.org/10.1145/335305.335358},
 
publisher = {ACM}
 
}
 
</bibtex></ref>
 
 
<ref name =Roth01><bibtex>
 
@phdthesis{Roth01,
 
  author =      "Paul W. K. Rothemund",
 
  school =      "University of Southern California",
 
  year =        "2001",
 
  month =      "December",
 
  title =      "Theory and Experiments in Algorithmic Self-Assembly",
 
}
 
</bibtex></ref>
 
 
<ref name =jSSADST><bibtex>
 
@article{jSSADST,
 
  author =  "James I. Lathrop and Jack H. Lutz and Scott M. Summers",
 
  title =    "Strict Self-Assembly of Discrete Sierpinski Triangles",
 
  journal = "Theoretical Computer Science",
 
  volume = "410",
 
  year = "2009",
 
  pages = "384--405"
 
}
 
note = "Preliminary version appeared in Proceedings of The Third Conference on Computability in Europe (Siena, Italy, June 18-23, 2007)"
 
</bibtex></ref>
 
 
<ref name =SolWin07><bibtex>
 
@article{SolWin07,
 
  author    = {David Soloveichik and
 
              Erik Winfree},
 
  title    = {Complexity of Self-Assembled Shapes},
 
  journal  = {SIAM Journal on Computing},
 
  volume    = {36},
 
  number    = {6},
 
  year      = {2007},
 
  pages    = {1544-1569},
 
  ee        = {http://dx.doi.org/10.1137/S0097539704446712},
 
  bibsource = {DBLP, http://dblp.uni-trier.de}
 
}
 
</bibtex></ref>
 
 
 
</references>
 

Revision as of 11:33, 11 June 2013

Building \(n \times n\) squares

Since Winfree showed in his thesis [1] that the aTAM is computationally universal, we know that we can algorithmically direct the growth of assemblies. This ability allows for not only the creation of complicated and precise shapes, but also often for them to be created very tile type efficiently (i.e. they require small tile sets - those with few numbers of unique tile types). A benchmark problem for tile-based self-assembly is that of assembling an \(n \times n\) square since this requires that the tiles somehow compute the value of \(n\) and thus "know when to stop" at the boundaries. In <ref name =RotWin00> Rothemund and Winfree showed that binary counters can be used to guide the growth of squares and that thereby it is possible to self-assemble an \(n \times n\) square using \(O(\log n)\) tile types.

  1. Cite error: Invalid <ref> tag; no text was provided for refs named Winf98