×

Self-assembly of infinite structures: a survey. (English) Zbl 1232.05050

In this paper some recent results related to the self-assembly of infinite structures in Winfree’s abstract tile assembly model (TAM) in the two-dimensional Euclidean space \({\mathbb{Z}}^{2}\) are surveyed. These results include impossibility results, as well as the construction of novel tile assembly systems that produce computationally interesting shapes and patterns. This can help to explore how fundamental aspects of the TAM, such as the inability of spatial locations to be reused and their immutability, affect and limit the constructions and computations that are achievable. Several open questions are also presented and motivated.

MSC:

05B45 Combinatorial aspects of tessellation and tiling problems
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Leonard Adleman, Towards a mathematical theory of self-assembly, Tech. report, University of Southern California, 2000.; Leonard Adleman, Towards a mathematical theory of self-assembly, Tech. report, University of Southern California, 2000.
[2] Adleman, Leonard; Cheng, Qi; Goel, Ashish; Huang, Ming-Deh, Running time and program size for self-assembled squares, (STOC’01: Proceedings of the thirty-third annual ACM Symposium on Theory of Computing. STOC’01: Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, New York, NY, USA (2001), ACM), 740-748 · Zbl 1323.68267
[3] Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, Paul W.K. Rothemund, Combinatorial optimization problems in self-assembly, in: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002, pp. 23-32.; Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, Paul W.K. Rothemund, Combinatorial optimization problems in self-assembly, in: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, 2002, pp. 23-32. · Zbl 1192.90151
[4] Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Complexities for generalized models of self-assembly, in: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2004.; Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Complexities for generalized models of self-assembly, in: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2004. · Zbl 1318.68088
[5] Florent Becker, Ivan Rapaport, Eric Rémila, Self-assembling classes of shapes with a minimum number of tiles, and in optimal time, in: Foundations of Software Technology and Theoretical Computer Science, FSTTCS, 2006, pp. 45-56.; Florent Becker, Ivan Rapaport, Eric Rémila, Self-assembling classes of shapes with a minimum number of tiles, and in optimal time, in: Foundations of Software Technology and Theoretical Computer Science, FSTTCS, 2006, pp. 45-56. · Zbl 1162.68466
[6] Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki, The power of nondeterminism in self-assembly, Tech. Report 1006.2897, Computing Research Repository, 2010.; Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki, The power of nondeterminism in self-assembly, Tech. Report 1006.2897, Computing Research Repository, 2010. · Zbl 1377.68081
[7] Ho-Lin Chen, Ashish Goel, Error free self-assembly with error prone tiles, in: Proceedings of the 10th International Meeting on DNA Based Computers, 2004.; Ho-Lin Chen, Ashish Goel, Error free self-assembly with error prone tiles, in: Proceedings of the 10th International Meeting on DNA Based Computers, 2004. · Zbl 1116.68448
[8] Cheng, Qi; Aggarwal, Gagan; Goldwasser, Michael H.; Kao, Ming-Yang; Schweller, Robert T.; de Espanés, Pablo Moisset, Complexities for generalized models of self-assembly, SIAM Journal on Computing, 34, 1493-1515 (2005) · Zbl 1088.68067
[9] Qi Cheng, Ashish Goel, Pablo Moisset de Espanés, Optimal self-assembly of counters at temperature two, in: Proceedings of the First Conference on Foundations of Nanoscience: Self-assembled Architectures and Devices, 2004.; Qi Cheng, Ashish Goel, Pablo Moisset de Espanés, Optimal self-assembly of counters at temperature two, in: Proceedings of the First Conference on Foundations of Nanoscience: Self-assembled Architectures and Devices, 2004.
[10] David Doty, Randomized self-assembly for exact shapes, in: Proceedings of the Fiftieth IEEE Conference on Foundations of Computer Science, FOCS, 2009.; David Doty, Randomized self-assembly for exact shapes, in: Proceedings of the Fiftieth IEEE Conference on Foundations of Computer Science, FOCS, 2009. · Zbl 1292.68155
[11] Doty, David; Gu, Xiaoyang; Lutz, Jack H.; Mayordomo, Elvira; Moser, Philippe, Zeta-Dimension, (Proceedings of the Thirtieth International Symposium on Mathematical Foundations of Computer Science (2005), Springer-Verlag), 283-294 · Zbl 1156.11331
[12] Doty, David; Patitz, Matthew J.; Summers, Scott M., Limitations of self-assembly at temperature 1, Theoretical Computer Science, 412, 145-158 (2011) · Zbl 1234.05052
[13] Doty, David; Patitz, Matthew J.; Summers, Scott M., Limitations of self-assembly at temperature 1, (Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming. Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming, Fayetteville, Arkansas, USA, June 8-11, 2009. Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming. Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming, Fayetteville, Arkansas, USA, June 8-11, 2009, Lecture Notes in Computer Science, vol. 5877 (2009)), 35-44 · Zbl 1273.68118
[14] Ming-Yang Kao, Robert T. Schweller, Reducing tile complexity for self-assembly through temperature programming, in: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, Jan. 2006, 2007, pp. 571-580.; Ming-Yang Kao, Robert T. Schweller, Reducing tile complexity for self-assembly through temperature programming, in: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, Jan. 2006, 2007, pp. 571-580. · Zbl 1192.90177
[15] Kao, Ming-Yang; Schweller, Robert T., Randomized self-assembly for approximate shapes, (Aceto, Luca; Damgärd, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor, International Colloqium on Automata, Languages, and Programming. International Colloqium on Automata, Languages, and Programming, ICALP. International Colloqium on Automata, Languages, and Programming. International Colloqium on Automata, Languages, and Programming, ICALP, Lecture Notes in Computer Science, vol. 5125 (2008), Springer), 370-384 · Zbl 1153.68561
[16] Kautz, Steven M.; Lathrop, James I., Self-assembly of the Sierpinski carpet and related fractals, (Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming. Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming, Fayetteville, Arkansas, USA, June 8-11, 2009. Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming. Proceedings of The Fifteenth International Meeting on DNA Computing and Molecular Programming, Fayetteville, Arkansas, USA, June 8-11, 2009, Lecture Notes in Computer Science, vol. 5877 (2009)), 78-87 · Zbl 1273.68127
[17] James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, Computability and complexity in self-assembly, Theory of Computing Systems (in press).; James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, Computability and complexity in self-assembly, Theory of Computing Systems (in press). · Zbl 1142.68352
[18] Lathrop, James I.; Lutz, Jack H.; Summers, Scott M., Strict self-assembly of discrete Sierpinski triangles, Theoretical Computer Science, 410, 384-405 (2009) · Zbl 1160.68012
[19] Lutz, Jack H.; Shutters, Brad, Approximate self-assembly of the Sierpinski triangle, (Proceedings of The Sixth Conference on Computability in Europe, Ponta Delgada, Portugal, June 30-July 4, 2010. Proceedings of The Sixth Conference on Computability in Europe, Ponta Delgada, Portugal, June 30-July 4, 2010, LNCS, vol. 6158 (2010), Springer), 286-295 · Zbl 1286.92037
[20] Urmi Majumder, Thomas H. LaBean, John H. Reif, Activatable tiles for compact error-resilient directional assembly, in: 13th International Meeting on DNA Computing (DNA 13), Memphis, Tennessee, June 4-8, 2007, 2007.; Urmi Majumder, Thomas H. LaBean, John H. Reif, Activatable tiles for compact error-resilient directional assembly, in: 13th International Meeting on DNA Computing (DNA 13), Memphis, Tennessee, June 4-8, 2007, 2007. · Zbl 1137.68398
[21] Matthew J. Patitz, Scott M. Summers, Self-assembly of decidable sets, Natural Computing (in press).; Matthew J. Patitz, Scott M. Summers, Self-assembly of decidable sets, Natural Computing (in press). · Zbl 1166.68329
[22] Patitz, Matthew J.; Summers, Scott M., Self-assembly of discrete self-similar fractals, Natural Computing, 9, 1, 135-172 (2010) · Zbl 1204.28016
[23] John H. Reif, Molecular assembly and computation: From theory to experimental demonstrations, in: Proceedings of the Twenty-Ninth International Colloquium on Automata, Languages and Programming, 2002, pp. 1-21.; John H. Reif, Molecular assembly and computation: From theory to experimental demonstrations, in: Proceedings of the Twenty-Ninth International Colloquium on Automata, Languages and Programming, 2002, pp. 1-21. · Zbl 1056.68544
[24] Paul W.K. Rothemund, Theory and experiments in algorithmic self-assembly, Ph.D. thesis, University of Southern California, December 2001.; Paul W.K. Rothemund, Theory and experiments in algorithmic self-assembly, Ph.D. thesis, University of Southern California, December 2001.
[25] Rothemund, Paul W. K.; Winfree, Erik, The program-size complexity of self-assembled squares (extended abstract), (STOC’00: Proceedings of the thirty-second annual ACM Symposium on Theory of Computing (2000), ACM: ACM New York, NY, USA), 459-468 · Zbl 1296.68051
[26] Rothemund, Paul W. K.; Papadakis, Nick; Winfree, Erik, Algorithmic self-assembly of DNA Sierpinski triangles, PLoS Biology, 2, 12, 2041-2053 (2004)
[27] Seeman, Nadrian C., Nucleic-acid junctions and lattices, Journal of Theoretical Biology, 99, 237-247 (1982)
[28] David Soloveichik, Erik Winfree, Complexity of compact proofreading for self-assembled patterns, in: The eleventh International Meeting on DNA Computing, 2005.; David Soloveichik, Erik Winfree, Complexity of compact proofreading for self-assembled patterns, in: The eleventh International Meeting on DNA Computing, 2005. · Zbl 1234.68158
[29] Soloveichik, David; Winfree, Erik, Complexity of self-assembled shapes, SIAM Journal on Computing, 36, 6, 1544-1569 (2007) · Zbl 1136.68029
[30] LaBean, Thomas; Majumder, Urmi; Sahu, Sudheer; Reif, John H., Design and simulation of self-repairing DNA lattices, (DNA Computing: DNA12. DNA Computing: DNA12, Lecture Notes in Computer Science, vol. 4287 (2006), Springer-Verlag) · Zbl 1132.68403
[31] Wang, Hao, Proving theorems by pattern recognition-II, The Bell System Technical Journal, XL, 1, 1-41 (1961)
[32] Wang, Hao, Dominoes and the AEA case of the decision problem, (Proceedings of the Symposium on Mathematical Theory of Automata. Proceedings of the Symposium on Mathematical Theory of Automata, New York, 1962 (1963), Polytechnic Press of Polytechnic Inst. of Brooklyn: Polytechnic Press of Polytechnic Inst. of Brooklyn Brooklyn, NY), 23-55 · Zbl 0137.01001
[33] Erik Winfree, Algorithmic self-assembly of DNA, Ph.D. thesis, California Institute of Technology, June 1998.; Erik Winfree, Algorithmic self-assembly of DNA, Ph.D. thesis, California Institute of Technology, June 1998.
[34] Erik Winfree, Simulations of computing by self-assembly, Tech. Report CaltechCSTR:1998.22, California Institute of Technology, 1998.; Erik Winfree, Simulations of computing by self-assembly, Tech. Report CaltechCSTR:1998.22, California Institute of Technology, 1998.
[35] Winfree, Erik; Bekbolatov, Renat, Proofreading tile sets: Error correction for algorithmic self-assembly, (Chen, Junghuei; Reif, John H., DNA. DNA, Lecture Notes in Computer Science, vol. 2943 (2003), Springer), 126-144 · Zbl 1098.68613
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.