The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
The program-size complexity of self-assembled squares (extended abstract)
Abstract
Molecular self-assembly gives rise to a great diversityofcomplex forms, from crystals and DNA helices to microtubules and holoenzymes. We study a formal model of pseudocrystalline self-assembly, called the Tile Assembly Model, in which atilemay be added to the growing object when the total interaction strength with its neighbors exceeds a parameter T. This model has been shown to be Turinguniversal. Thus, self-assembled objects can be studied from the point of view of computational complexity. Here, we dene the program size complexity ofanNN square to be the minimum number of distinct tiles required to self-assemble the square and no other objects. We study this complexity under the Tile Assembly Model and nd a dramatic decrease in complexity, from N 2 tiles to O(log N) tiles,asT is increased from 1 (where bonding is noncooperative) to 2 (allowing cooperative bonding). Further, we nd that the size of the largest square uniquely produced by a set of n tiles grows faster than any computable function. 1.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Metallic Phase with Long-Range Orientational Order and No Translational Symmetry
Shechtman, D., Blech, I., Gratias, D., & Cahn, J. W. (1984) · Physical Review Letters · doi:10.1103/physrevlett.53.1951 · Cited by 7,060
Molecular Computation of Solutions to Combinatorial Problems
Adleman, L. M. (1994) · Science · doi:10.1126/science.7973651 · Cited by 4,474
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (2019) · Texts in Computer Science · doi:10.1007/978-3-030-11298-1 · Cited by 3,681
Design and self-assembly of two-dimensional DNA crystals
Winfree, E., Liu, F., Wenzler, L. A., & Seeman, N. C. (1998) · Nature · doi:10.1038/28998 · Cited by 2,857
Self-citationThe thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (1997) · Springer eBooks · doi:10.1007/978-1-4757-2606-0 · Cited by 1,775
Proving Theorems by Pattern Recognition - II
Wang, H. (1961) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1961.tb03975.x · Cited by 862
Senechal, M. (1995) · Cited by 851
Undecidability and nonperiodicity for tilings of the plane
Robinson, R. M. (1971) · Inventiones mathematicae · doi:10.1007/bf01418780 · Cited by 826
Crystal Growth for Beginners: Fundamentals of Nucleation, Crystal Growth and Epitaxy
Markov, I. V. (2003) · WORLD SCIENTIFIC eBooks · doi:10.1142/5172 · Cited by 693
Self-Assembly of Mesoscale Objects into Ordered Two-Dimensional Arrays
Bowden, N., Terfort, A., Carbeck, J., & Whitesides, G. M. (1997) · Science · doi:10.1126/science.276.5310.233 · Cited by 660
DNA NANOTECHNOLOGY: Novel DNA Constructions
Seeman, N. C. (1998) · Annual Review of Biophysics and Biomolecular Structure · doi:10.1146/annurev.biophys.27.1.225 · Cited by 398
Crystal Growth for Beginners: Fundamentals of Nucleation, Crystal Growth and Epitaxy
Markov, I. V. (1995) · WORLD SCIENTIFIC eBooks · doi:10.1142/2145 · Cited by 394
Rado, T. (1962) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1962.tb00480.x · Cited by 297
Bowden, N., Choi, I. S., Grzybowski, B. A., & Whitesides, G. M. (1999) · Journal of the American Chemical Society · doi:10.1021/ja983882z · Cited by 221
On the computational power of DNA annealing and ligation
Winfree, E. (1996) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/027/09 · Cited by 197
Self-citationSimulations of Computing by Self-Assembly
Winfree, E. (1998) · CaltechAUTHORS (California Institute of Technology) · doi:10.7907/z9tb14x7 · Cited by 147
Self-citationMathematical Theory of Automata.
Fox, J. (1963) · Cited by 146
Chemical Kinetics is Turing Universal
Magnasco, M. O. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.1190 · Cited by 144
Using lateral capillary forces to compute by self-assembly
Rothemund, P. W. K. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.97.3.984 · Cited by 134
Self-citationDominoes and the Aea Case of the Decision Problem
Wang, H. (1990) · Springer eBooks · doi:10.1007/978-94-009-2356-0_11 · Cited by 99
Global order from local sources
Radin, C. (1991) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-1991-16077-5 · Cited by 84
Implementation of logic functions and computations by chemical kinetics
Hjelmfelt, A., & Ross, J. (1995) · Physica D Nonlinear Phenomena · doi:10.1016/0167-2789(95)00014-u · Cited by 55
Cited by
Algorithmic Self-Assembly of DNA Sierpinski Triangles
Rothemund, P. W. K., Papadakis, N., & Winfree, E. (2004) · PLoS Biology · doi:10.1371/journal.pbio.0020424 · Cited by 860
Self-citationDesign and Characterization of Programmable DNA Nanotubes
Rothemund, P. W. K., Ekani-Nkodo, A., Papadakis, N., Kumar, A., Fygenson, D. K., & Winfree, E. (2004) · Journal of the American Chemical Society · doi:10.1021/ja044319l · Cited by 512
Self-citationDiverse and robust molecular algorithms using reprogrammable DNA self-assembly
Woods, D., Doty, D., Myhrvold, C., Hui, J., Zhou, F., Yin, P., & Winfree, E. (2019) · Nature · doi:10.1038/s41586-019-1014-9 · Cited by 295
Self-citationAn information-bearing seed for nucleating algorithmic self-assembly
Barish, R. D., Schulman, R., Rothemund, P. W. K., & Winfree, E. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0808736106 · Cited by 267
Self-citation
Metadata
- Authors
- Rothemund, P. W. K., & Winfree, E.
- Venue
- Proceedings of the thirty-second annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2000-05
- Pages
- 459-468
- OpenAlex
- W1983241546
- Cited by
- 407
- References
- 23
- FWCI
- 10.74
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.