Adleman, L.M., Cheng, Q., Goel, A. and Huang, M-D. Running time and program size for self-assembled squares. In Proceedings of STOC (2001), 40--748.

Digital Library

Google Scholar

[3]

Adleman, L.M., Cheng, Q., Goel, A. and Huang, M-D., Kempe, D., de Espanés, P.M. and Rothemund, P.W.K. Combinatorial optimization problems in self-assembly. In Proceedings of STOC (2002), 23--32.

Digital Library

Google Scholar

[4]

Adleman, L.M, Kari, J., Kari, L., Reishus, D. and Sosik, P. The undecidability of the infinite ribbon problem: Implications for computing by self-assembly. SIAM Journal on Computing 38, 6 (2009), 2356--2381. Preliminary version appeared in FOCS 2002.

Digital Library

Google Scholar

[5]

Aggarwal, G. Cheng, Q., Goldwasser, M.H., Kao, M-Y., de Espanés, P.M. and Schweller, R.T. Complexities for generalized models of self-assembly. SIAM Journal on Computing 34 (2005), 1493--1515. Preliminary version appeared in In Proceedings of SODA 2004.

Digital Library

Google Scholar

[6]

Barish, R.D., Rothemund, P.W.K. and Winfree, E. Two computational primitives for algorithmic self-assembly: Copying and counting. Nano Letters 5 (2005), 2586--2592.

Crossref

Google Scholar

[7]

Barish, R.D, Schulman, R., Rothemund, P.W.K. and Winfree, E. An information-bearing seed for nucleating algorithmic self-assembly. In Proceedings of the National Academy of Sciences 106, 15 (Mar. 2009), 6054--6059.

Crossref

Google Scholar

[8]

Becker, F. Pictures worth a thousand tiles, a geometrical programming language for self-assembly. Theoretical Computer Science 410, 16 (2009), 1495--1515.

Digital Library

Google Scholar

[9]

Becker, F., Rapaport, I. and Rémila, E. Self-assembling classes of shapes with a minimum number of tiles, and in optimal time. In Proceedings of FSTTCS (2006), 45--56.

Digital Library

Google Scholar

[10]

Bryans, N., Chiniforooshan, E., Doty, D., Kari, L. and Seki, S. The power of nondeterminism in self-assembly. Theory of Computing, To appear. Preliminary version appeared in Proceedings of SODA (2011), 590--602.

Digital Library

Google Scholar

[11]

Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat S., Patitz, M.J., Schweller, R.T., Summers, S.M. and Winslow, A. Two hands are better than one (up to constant factors). Technical Report 1201.1650, Computing Research Repository, 2012.

Google Scholar

[12]

Chandran, H., Gopalkrishnan, N. and Reif, J.H. The tile complexity of linear assemblies. In SIAM Journal on Computing 41, 4 (2012) 1051--1073. Preliminarly version appeared in ICALP (2009).

Digital Library

Google Scholar

[13]

Chen, H.-L. and Doty, D. Parallelism and time in hierarchical self-assembly. In Proceedings of SODA (2012), 1163--1182.

Digital Library

Google Scholar

[14]

Chen, H.-L. and Goel, A. Error free self-assembly with error prone tiles. DNA 2004.

Digital Library

Google Scholar

[15]

Chen, H.-L., Goel, A. and Luhrs, C. Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly. In Proceedings of SODA (2008), 409--418.

Digital Library

Google Scholar

[16]

Chen, H.-L., Goel, A. and Luhrs, C. and Winfree, E. Self-assembling tile systems that heal from small fragments. DNA (2007), 30--46.

Google Scholar

[17]

Chen, H.-L., Schulman, R., Goel, A. and Winfree, E. Reducing facet nucleation during algorithmic self-assembly. Nano Letters 7, 9 (Sept. 2007), 2913--2919.

Crossref

Google Scholar

[18]

Cook, M., Fu, Y. and Schweller, R.T. Temperature 1 self-assembly: Deterministic assembly in 3D and probabilistic assembly in 2D. In Proceedings of SODA (2011), 570--589.

Digital Library

Google Scholar

[19]

Cook, M., Rothemund, P. and Winfree, E. Self-assembled circuit patterns. DNA (2004), 1979--1979.

Google Scholar

[20]

Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M. Rafalin, E., Schweller, R.T. and Souvaine, D.L. Staged self-assembly: Nanomanufacture of arbitrary shapes with 0(1) glues. Natural Computing 7, 3 (2008), 347--370. Preliminary version appeared in DNA (2007).

Digital Library

Google Scholar

[21]

Demaine, E.D., Eisenstat, S., Ishaque, M. and Winslow, A. 0ne-dimensional staged self-assembly. DNA (2011), 100--114.

Digital Library

Google Scholar

[22]

Demaine, E.D., Patitz, M.J., Schweller, R.T. and Summers, S.M. Self-assembly of arbitrary shapes using RNAse enzymes: Meeting the Kolmogorov bound with small scale factor. In Proceedings of STACS (2011).

Google Scholar

[23]

Doty, D. Randomized self-assembly for exact shapes. SIAM Journal on Computing, 39, 8 (2010), 3521--3552. Preliminary version appeared in Proceedings of FOCS (2009).

Digital Library

Google Scholar

[24]

Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R.T., Summers, M. and Woods, D. The tile assembly model is intrinsically universal. In Proceedings of FOCS (2012), to appear. IEEE.

Digital Library

Google Scholar

[25]

Doty, D. and Patitz, M.J. A domain-specific language for programming in the tile assembly model. Proceedings of DNA (2009), 25--34.

Digital Library

Google Scholar

[26]

Doty, D. and Patitz, M.J., Reishus, D., Schweller, R.T. and Summers, S.M. Strong fault-tolerance for self-assembly with fuzzy temperature. In Proceedings of FOCS (2010), IEEE, 417--426.

Digital Library

Google Scholar

[27]

Doty, D. and Patitz, M.J. and Summers, S.M. Limitations of self-assembly at Temperature 1. Theoretical Computer Science 412, 1--2 (Jan. 2011), 145--158. Preliminary version appeared in DNA (2009).

Digital Library

Google Scholar

[28]

Fujibayashi, K., Hariadi, R., Park, S.H., Winfree, E. and Murata, S. Toward reliable algorithmic self-assembly of DNA tiles: A fixed-width cellular automaton pattern. Nano Letters 8, 7 (2007), 1791--1797.

Google Scholar

[29]

Fujibayashi, K., Zhang, D., Winfree, E. and Murata, S. Error suppression mechanisms for DNA tile self-assembly and their simulation. Natural Computing 8, 3 (2009), 589--612.

Digital Library

Google Scholar

[30]

Göös, M. and Orponen, P. Synthesizing minimal tile sets for patterned DNA self-assembly. DNA (2010), 71--82.

Digital Library

Google Scholar

[31]

Kao, M.-Y. and Schweller, R.T. Reducing tile complexity for self-assembly through temperature programming. In Proceedings of SODA (2006), 571--580.

Digital Library

Google Scholar

[32]

Kao, M.-Y. and Schweller, R.T. Randomized self-assembly for approximate shapes. In Proceedings of ICALP (2008), 370--384.

Digital Library

Google Scholar

[33]

Kolmogorov, A.N. Three approaches to the quantitative definition of 'information.' Problems of Information Transmission 1:1 (1965), 7.

Google Scholar

[34]

Lathrop, J. Lutz, J., Patitz, M. and Summers, S. Computability and complexity in self-assembly. Theory of Computing Systems 48 (2011), 617--647. Preliminary version appeared in CiE (2008).

Digital Library

Google Scholar

[35]

Lempiäinen, T., Czeizler, E. and Orponen, P. Synthesizing small and reliable tile sets for patterned DNA self-assembly. DNA (2011), 145--159.

Digital Library

Google Scholar

[36]

Majumder, U., LaBean, T.H. and Reif, J.H. Activatable tiles for compact error-resilient directional assembly. DNA (2007), 15--25.

Google Scholar

[37]

Maňuch, J., Stacho, L. and Stoll, C. Step-assembly with a constant number of tile types. In Proceedings of ISAAC (2009), 954--963.

Digital Library

Google Scholar

[38]

Maňuch, J., Stacho, L. and Stoll, C. Two lower bounds for self-assemblies at Temperature 1. Journal of Computational Biology 17, 6 (2010), 841--852.

Crossref

Google Scholar

[39]

Padilla, J.E., Liu, W. and Seeman, N.C. Hierarchical self-assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model. Natural Computing 11, 2 (2012), 323--338.

Digital Library

Google Scholar

[40]

Patitz, M.J. Simulation of self-assembly in the abstract tile assembly model with ISU TAS. FNANO (2009), 209--219.

Google Scholar

[41]

Patitz, M.J., Schweller, R.T. and Summers, S.M. Exact shapes and Turing universality at Temperature 1 with a single negative glue. DNA (2011), 175--189.

Digital Library

Google Scholar

[42]

Patitz, M.J. and Summers, S.M. Self-assembly of decidable sets. Natural Computing 10 (2011), 853--877. Preliminary version appeared in UC 2008.

Digital Library

Google Scholar

[43]

Reif, J.H. Local parallel biomolecular computation. DNA 3 (1999), 217--254.

Google Scholar

[44]

Reif, J. Sahu, S. and Yin, P. Compact error-resilient computational DNA tiling assemblies. DNA 2004.

Digital Library

Google Scholar

[45]

Rothemund, P.W.K. Folding DNA to create nanoscale shapes and patterns. Nature 440, 7082 (2006), 297--302.

Crossref

Google Scholar

[46]

Rothemund, P.W.K., Papadakis, N. and Winfree, E. Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology 2, 12 (2004), 2041--2053.

Crossref

Google Scholar

[47]

Rothemund, P.W.K. and Winfree, E. The program-size complexity of self-assembled squares (extended abstract). In Proceedings of STOC (2000), 459--468.

Digital Library

Google Scholar

[48]

Schulman, R. and Winfree, E. Programmable control of nucleation for algorithmic self-assembly. SIAM Journal on Computing 39, 4 (2009), 1581--1616. Preliminary version appeared in DNA (2004).

Digital Library

Google Scholar

[49]

Schulman, R. and Winfree, E. Synthesis of crystals with a programmable kinetic barrier to nucleation. In Proceedings of the National Academy of Sciences 104, 39 (2007), 15236--15241.

Crossref

Google Scholar

[50]

Soloveichik, D., Cook, M. and Winfree, E. Combining self-healing and proofreading in self-assembly. Natural Computing 7, 2 (2008), 203--218.

Digital Library

Google Scholar

[51]

Soloveichik, D. and Winfree, E. Complexity of compact proofreading for self-assembled patterns. DNA (2005).

Digital Library

Google Scholar

[52]

Soloveichik, D. and Winfree, E. Complexity of self-assembled shapes. SIAM Journal on Computing 36, 6 (2007), 1544--1569. Preliminary version appeared in DNA (2004).

Digital Library

Google Scholar

[53]

Summers, S.M. Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica 63, 1 (2012) 117--136.

Digital Library

Google Scholar

[54]

Turing, A.M. On computable numbers, with an application to the Entscheidungsproblem. In Proceedings of the London Mathematical Society (1936), 230--265.

Google Scholar

[55]

Winfree, E. Simulations of computing by self-assembly. Technical Report Caltech CSTR:1998.22. California Institute of Technology, 1998.

Google Scholar

[56]

Winfree, E. Algorithmic Self-Assembly of DNA. Ph.D. thesis, California Institute of Technology, June 1998.

Digital Library

Google Scholar

[57]

Winfree, E. Self-healing tile sets. Nanotechnology: Science and Computation, Natural Computing Series. J. Chen, N. Jonoska, and G. Rozenberg, eds. Springer, 2006, 55--78.

Google Scholar

[58]

Winfree, E. and Bekbolatov, R. Proofreading tile sets: Error correction for algorithmic self-assembly. DNA (2003), 126--144.

Google Scholar

[59]

Winfree, E., Liu, F., Wenzler, L.A. and Seeman, N.C. Design and self-assembly of two-dimensional DNA crystals. Nature 394, 6693 (1998), 539--544.

Crossref

Google Scholar

Cited By

View all

Connor MMichail O(2025)Transformation of Modular Robots by Rotation: 3 + 1 Musketeers for all Orthogonally Convex ShapesJournal of Computer and System Sciences10.1016/j.jcss.2024.103618(103618)Online publication date: Jan-2025
https://doi.org/10.1016/j.jcss.2024.103618
Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2025)The complexity of growing a graphJournal of Computer and System Sciences10.1016/j.jcss.2024.103587147(103587)Online publication date: Feb-2025
https://doi.org/10.1016/j.jcss.2024.103587
Függer MNowak TRybicki JKuznetsov PGelles ROlivetti D(2024)Majority Consensus Thresholds in Competitive Lotka-Volterra PopulationsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662823(76-86)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662823
Show More Cited By

Index Terms

Theory of algorithmic self-assembly
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Design and analysis of algorithms
  2. Models of computation

Recommendations

Algorithmic DNA self-assembly
AAIM'06: Proceedings of the Second international conference on Algorithmic Aspects in Information and Management

Self-assembly is the ubiquitous process by which objects autonomously assemble into complexes. This phenomenon is common in nature and yet is poorly understood from mathematical and programming perspectives. It is believed that self-assembly technology ...
Universality in algorithmic self-assembly
Programmable Control of Nucleation for Algorithmic Self-Assembly

Algorithmic self-assembly, a generalization of crystal growth processes, has been proposed as a mechanism for autonomous DNA computation and for bottom-up fabrication of complex nanostructures. A “program” for growing a desired structure consists of a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 55, Issue 12

December 2012

102 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/2380656

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2012

Published in CACM Volume 55, Issue 12

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Funding Sources

Division of Computing and Communication Foundations

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

109
Total Citations
View Citations
7,922
Total Downloads

Downloads (Last 12 months)498
Downloads (Last 6 weeks)66

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Connor MMichail O(2025)Transformation of Modular Robots by Rotation: 3 + 1 Musketeers for all Orthogonally Convex ShapesJournal of Computer and System Sciences10.1016/j.jcss.2024.103618(103618)Online publication date: Jan-2025
https://doi.org/10.1016/j.jcss.2024.103618
Mertzios GMichail OSkretas GSpirakis PTheofilatos M(2025)The complexity of growing a graphJournal of Computer and System Sciences10.1016/j.jcss.2024.103587147(103587)Online publication date: Feb-2025
https://doi.org/10.1016/j.jcss.2024.103587
Függer MNowak TRybicki JKuznetsov PGelles ROlivetti D(2024)Majority Consensus Thresholds in Competitive Lotka-Volterra PopulationsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662823(76-86)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662823
Piantanida LLiddle JHughes WMajikes J(2024)DNA nanostructure decoration: a how-to tutorialNanotechnology10.1088/1361-6528/ad2ac535:27(273001)Online publication date: 23-Apr-2024
https://doi.org/10.1088/1361-6528/ad2ac5
Almalki NMichail O(2024)On geometric shape construction via growth operationsTheoretical Computer Science10.1016/j.tcs.2023.114324984(114324)Online publication date: Feb-2024
https://doi.org/10.1016/j.tcs.2023.114324
Yu SXu WLee JIsokawa T(2024)A Cellular Automaton Approach for Efficient Computing on Surface Chemical Reaction NetworksNew Generation Computing10.1007/s00354-024-00262-542:2(217-235)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00354-024-00262-5
Almalki NGupta SMichail O(2024)On the Exponential Growth of Geometric ShapesAlgorithmics of Wireless Networks10.1007/978-3-031-74580-5_2(16-30)Online publication date: 5-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-74580-5_2
Arellanes D(2024)Composition Machines: Programming Self-organising Software Models for the Emergence of Sequential Program SpacesTheoretical Aspects of Software Engineering10.1007/978-3-031-64626-3_2(19-37)Online publication date: 29-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-64626-3_2
Nokhanji NFlocchini PSantoro N(2023)Dynamic Line Maintenance by Hybrid Programmable MatterInternational Journal of Networking and Computing10.15803/ijnc.13.1_1813:1(18-47)Online publication date: 2023
https://doi.org/10.15803/ijnc.13.1_18
Tobiason MYurke BHughes W(2023)Generation of DNA oligomers with similar chemical kinetics via in-silico optimizationCommunications Chemistry10.1038/s42004-023-01026-w6:1Online publication date: 18-Oct-2023
https://doi.org/10.1038/s42004-023-01026-w
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Algorithmic DNA self-assembly

Universality in algorithmic self-assembly

Programmable Control of Nucleation for Algorithmic Self-Assembly

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Digital Edition

Magazine Site

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations