ACM Home Page
Please provide us with feedback. Feedback
The program-size complexity of self-assembled squares (extended abstract)
Full text PdfPdf (973 KB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents
Portland, Oregon, United States
Pages: 459 - 468  
Year of Publication: 2000
ISBN:1-58113-184-4
Authors
Paul W. K. Rothemund  Dept. of Computer Science, University of Southern California
Erik Winfree  Dept. of Computer Science and CNS, California Institute of Technology
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 5,   Downloads (12 Months): 67,   Citation Count: 31
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335358
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
 
2
Adleman, L. M. (unpublished manuscript, 2000). Toward a mathematical theory of self-assembly.
 
3
Bennett, C. H. (1982). The thermodynamics of computation- a review. International Journal of Theoretical Physics, 21(12):905-940.
 
4
Berger, R. (1966). The undecidability of the domino problem. Memiors of the AMS, 66:1-72.
 
5
Bowden, N., Choi, I., Gryzbowski, B., and Whitesides, G. (1999). Mesoscale self-assembly of hexagonal plates using lateral capillary forces: Synthesis using the "capillary bond". Journal of the American Chemical Society, 121:5373-5391.
 
6
Bowden, N., Terfort, A., Carbeck, j., and Whitesides, G. (1997). Self-assembly of mesoscaJe objects into ordered two-dimensional arrays. Science, 276:233-235.
 
7
 
8
Hosokawa, K., Shimoyama, I., and Miura, H. (1996). Two-dimensional micro-self-assembly using the surface tension of water. Sensors and Actuators A, 57:117-125.
 
9
 
10
 
11
Mackay, A. (1995). Generalised crystallography, journal of Molecular Structure (Theochem), 336:293-303.
 
12
Magnasco, M. O. (1997). Chemical kinetics is Turing universal. Physical Review Letters, 78(6):1190-1193.
 
13
Markov, I. V. (1995). Crystal Growth for Beginners: fundamentals of nucleation, crystal growth, and epitaxy. World Scientific, Singapore.
 
14
Ptashne, M. (1992). A Genetic Switch, 2nd ed. Cell Press & Blackwell.
 
15
Radin, C. (1991). Global order from local sources. Bulletin of the AMS, 25(2):335-364.
 
16
Rado, T. (1962). Oa non-computable functions. Bell System Technical Yvurnal, 41(3):877-884.
 
17
Robinson, R. M. (1971). Undecidability and nonperiodicity of tilings of the plane. Inventiones Math., 12:177-209.
 
18
Rothemund, P. W. K. (2000). Using lateral capillary forces to compute by self-assembly. Proceedings of the National Academy of Sciences, 97:984-989.
 
19
Schectman, D., Blech, I., Gratias, D., and Cahn, J. (1984). Metallic phase with long-range orientational order and no translational symmetry. Phys. Rev. Lett., 53:1951-1953.
 
20
Seeman, N. C. (1998). DNA nanotechnology: novel DNA constructions. Annual Review of Biophysics and Biomolecular Structure, 27:225-248.
 
21
SenechaJ, M. (1995). Quasicrystals and geometry. Cambridge University Press, Cambridge.
 
22
Wang, H. (1961). Proving theorems by pattern recognition. Ii. Bell System Technical Journal, 40:1-42.
 
23
Wang, H. (1963). Dominoes and the AEA case of the decision problem. In Fox, J., editor, Mathematical Theory of Automata, pages 23-55, Brooklyn, New York. Polytechnic Press.
 
24
Winfree, E. (1996). On the computational power of DNA annealing and ligation. In Lipton, R. J. and Baum, E. B., editors, DNA Based Computers: DIMAC$ Workshop, April J, 1995, volume 27, pages 199-221, Providence, RI. American Mathematical Society.
 
25
Winfree, E. (preliminary, 1998). Simulations of computing by self-assembly. In Karl, L., Rubin, H., and Wood, D. H., editors, Proceedings of the 4th DiMAC$ Meeting on DNA Based Computers, held at the University of Pennsylvania, June 16-19, 1998.
 
26
Winfree, E., Liu, F., Wenzler, L. A., and Seeman, N. C. (1998a). Design and self-assembly of two-dimensional DNA crystals. Nature, 394:539-544.
 
27
Winfree, E., Yang, X., and Seeman, N. C. (1998b). Universal computation via self-assembly of DNA: Some theory and experiments. In Landweber, L. F. and Baum, E. B., editors, DNA Based Computers H: DIMACS Workshop, June 10-12, 1996, volume 44, Providence, Ri. American Mathematical Society.

CITED BY  31

Collaborative Colleagues:
Paul W. K. Rothemund: colleagues
Erik Winfree: colleagues