The program-size complexity of self-assembled squares (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The program-size complexity of self-assembled squares (extended abstract)

Full text

Pdf (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): 12, Downloads (12 Months): 54, Citation Count: 30

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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	Leonard M. Adleman, Molecular computation of solutions to combinatorial problems, Science, v.266 n.11, p.1021-1024, Nov. 1994
	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	A. Hjelmfelt , J. Ross, Implementation of logic functions and computations by chemical kinetics, Physica D, v.84 n.1-2, p.180-193, June 15, 1995 [doi>10.1016/0167-2789(95)00014-U]
	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	Stuart A. Kurtz , Stephen R. Mahaney , James S. Royer , Janos Simon, Biological computing, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
	10	Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	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 30

	Ján Maňuch , Ladislav Stacho , Christine Stoll, Two lower bounds for self-assemblies at temperature 1, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Gagan Aggarwal , Michael H. Goldwasser , Ming-Yang Kao , Robert T. Schweller, Complexities for generalized models of self-assembly, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Leonard Adleman , Qi Cheng , Ashish Goel , Ming-Deh Huang, Running time and program size for self-assembled squares, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.740-748, July 2001, Hersonissos, Greece
	David Soloveichik , Matthew Cook , Erik Winfree, Combining self-healing and proofreading in self-assembly, Natural Computing: an international journal, v.7 n.2, p.203-218, June 2008
	Ho-Lin Chen , Qi Cheng , Ashish Goel , Ming-Deh Huang , Pablo Moisset de Espanés, Invadable self-assembly: combining robustness with efficiency, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Yuliy Baryshnikov , Ed Coffman , Petar Momčilović, Self assembly times in DNA-based computation, ACM SIGMETRICS Performance Evaluation Review, v.32 n.2, September 2004
	Ming-Yang Kao , Robert Schweller, Reducing tile complexity for self-assembly through temperature programming, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.571-580, January 22-26, 2006, Miami, Florida
	Erik D. Demaine , Martin L. Demaine , Sándor P. Fekete , Mashhood Ishaque , Eynat Rafalin , Robert T. Schweller , Diane L. Souvaine, Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues, Natural Computing: an international journal, v.7 n.3, p.347-370, September 2008
	Pablo Moisset De Espanés , Ashish Goel, Toward minimum size self-assembled counters, Natural Computing: an international journal, v.7 n.3, p.317-334, September 2008
	Florent Becker, Pictures worth a thousand tiles, a geometrical programming language for self-assembly, Theoretical Computer Science, v.410 n.16, p.1495-1515, April, 2009
	James I. Lathrop , Jack H. Lutz , Scott M. Summers, Strict self-assembly of discrete Sierpinski triangles, Theoretical Computer Science, v.410 n.4-5, p.384-405, February, 2009
	A. Murugan , K. S. Easwarakumar, DNA algorithms for fractal construction-an application of the SInsDelP system, International Journal of Computer Mathematics, v.84 n.4, p.437-450, April 2007
	Takashi Yokomori , Yasubumi Sakakibara , Satoshi Kobayashi, A magic pot: self-assembly computation revisited, Formal and natural computing, Springer-Verlag New York, Inc., New York, NY, 2002
	Ho-Lin Chen , Ashish Goel , Chris Luhrs, Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.409-418, January 20-22, 2008, San Francisco, California
	Masoud Hashempour , Zahra Mashreghian Arani , Fabrizio Lombardi, Healing DNA Self-Assemblies Using Punctures, Journal of Electronic Testing: Theory and Applications, v.25 n.1, p.25-37, February 2009
	Francesco Bernardini , Robert Brijder , Grzegorz Rozenberg , Claudio Zandron, Multiset-Based Self-Assembly of Graphs, Fundamenta Informaticae, v.75 n.1-4, p.49-75, January 2007
	Yuriy Brun , Nenad Medvidovic, An Architectural Style for Solving Computationally Intensive Problems on Large Networks, Proceedings of the 2007 International Workshop on Software Engineering for Adaptive and Self-Managing Systems, p.2, May 20-26, 2007
	Yuriy Brun, Solving satisfiability in the tile assembly model with a constant-size tileset, Journal of Algorithms, v.63 n.4, p.151-166, October, 2008
	Len Adleman , Qi Cheng , Ashish Goel , Ming-Deh Huang , David Kempe , Pablo Moisset de Espanés , Paul Wilhelm Karl Rothemund, Combinatorial optimization problems in self-assembly, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Yuriy Brun, Arithmetic computation in the tile assembly model: Addition and multiplication, Theoretical Computer Science, v.378 n.1, p.17-31, June, 2007
	Yuriy Brun , Nenad Medvidovic, Fault and adversary tolerance as an emergent property of distributed systems' software architectures, Proceedings of the 2007 workshop on Engineering fault tolerant systems, p.7-es, September 04-04, 2007, Dubrovnik, Croatia
	Rebecca Schulman , Erik Winfree, How crystals that sense and respond to their environments could evolve, Natural Computing: an international journal, v.7 n.2, p.219-237, June 2008
	Nataa Jonoska , Gregory L. McColm, Complexity classes for self-assembling flexible tiles, Theoretical Computer Science, v.410 n.4-5, p.332-346, February, 2009
	Stanislav Angelov , Sanjeev Khanna , Mirkó Visontai, On the complexity of graph self-assembly in accretive systems, Natural Computing: an international journal, v.7 n.2, p.183-201, June 2008
	Yuriy Brun, Nondeterministic polynomial time factoring in the tile assembly model, Theoretical Computer Science, v.395 n.1, p.3-23, April, 2008
	Yuriy Brun, Solving NP-complete problems in the tile assembly model, Theoretical Computer Science, v.395 n.1, p.31-46, April, 2008
	Yuriy Brun , Dustin Reishus, Path finding in the tile assembly model, Theoretical Computer Science, v.410 n.15, p.1461-1472, April, 2009
	Anand Panangadan , Michael G. Dyer, Construction in a Simulated Environment Using Temporal Goal Sequencing and Reinforcement Learning, Adaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems, v.17 n.1, p.81-104, February 2009
	John H. Reif, The emerging discipline of biomolecular computation in the US, New Generation Computing, v.20 n.3, p.217-236, July 2002
	Takashi Yokomori, Molecular computing paradigm – toward freedom from Turing's charm, Natural Computing: an international journal, v.1 n.4, p.333-390, 2002