[1]   Zachary Abel, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Scott D. Kominers, and Robert T. Schweller: Shape replication through self-assembly and RNase enzymes. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 1045–1064. ACM Press, 2010. [ACM:1873601.1873686]

[2]   Leonard M. Adleman: Towards a mathematical theory of self-assembly. Technical report, University of Southern California, 2000.

[3]   Leonard M. Adleman, Qi Cheng, Ashish Goel, and Ming-Deh A. Huang: Running time and program size for self-assembled squares. In Proc. 33rd STOC, pp. 740–748. ACM Press, 2001. [doi:10.1145/380752.380881]

[4]   Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, and Paul W. K. Rothemund: Combinatorial optimization problems in self-assembly. In Proc. 34th STOC, pp. 23–32. ACM Press, 2002. [doi:10.1145/509907.509913]

[5]   Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanés, and Robert T. Schweller: Complexities for generalized models of self-assembly. SIAM J. Comput., 34(6):1493–1515, 2005. Preliminary version in SODA’04. [doi:10.1137/S0097539704445202]

[6]   Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

[7]   Robert D. Barish, Rebecca Schulman, Paul W. K. Rothemund, and Erik Winfree: An information-bearing seed for nucleating algorithmic self-assembly. Proc. Nat. Acad. Sci., 106(15):6054–6059, 2009. [doi:10.1073/pnas.0808736106]

[8]   Florent Becker, Ivan Rapaport, and Éric Rémila: Self-assemblying classes of shapes with a minimum number of tiles, and in optimal time. In 26th Internat. Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS’06), pp. 45–56, 2006. [doi:10.1007/11944836_7]

[9]   Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki: The power of nondeterminism in self-assembly. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 590–602. ACM Press, 2011. [ACM:2133082]

[10]   Harish Chandran, Nikhil Gopalkrishnan, and John H. Reif: Tile complexity of linear assemblies. SIAM J. Comput., 41(4):1051–1073, 2012. Preliminary version in ICALP’09. [doi:10.1137/110822487]

[11]   Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine: Staged self-assembly: Nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing, 7(3):347–370, 2008. Preliminary version in DNA’07. [doi:10.1007/s11047-008-9073-0]

[12]   Erik D. Demaine, Sarah Eisenstat, Mashhood Ishaque, and Andrew Winslow: One-dimensional staged self-assembly. In 17th Internat. Conf. DNA Computing and Molecular Programming (DNA’11), pp. 100–114, 2011. [doi:10.1007/978-3-642-23638-9_10]

[13]   Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers: Self-assembly of arbitrary shapes using RNAse enzymes: Meeting the Kolmogorov bound with small scale factor. In Proc. 28th Symp. Theoretical Aspects of Comp. Sci. (STACS’11), pp. 201–212, 2011. [doi:10.4230/LIPIcs.STACS.2011.201]

[14]   David Doty: Randomized self-assembly for exact shapes. SIAM J. Comput., 39(8):3521–3552, 2010. Preliminary version in FOCS’09. [doi:10.1137/090779152]

[15]   David Doty: Theory of algorithmic self-assembly. Comm. ACM, 55(12):78–88, 2012. [doi:10.1145/2380656.2380675]

[16]   David Doty, Matthew J. Patitz, and Scott M. Summers: Limitations of self-assembly at temperature 1. Theoret. Comput. Sci., 412(1-2):145–158, 2011. Preliminary version in DNA’09. [doi:10.1016/j.tcs.2010.08.023]

[17]   Constantine Evans: Personal communication.

[18]   Steven Fortune: A note on sparse complete sets. SIAM J. Comput., 8(3):431–433, 1979. [doi:10.1137/0208034]

[19]   Bin Fu, Matthew J. Patitz, Robert T. Schweller, and Robert Sheline: Self-assembly with geometric tiles. In Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP’12), pp. 714–725, 2012. [doi:10.1007/978-3-642-31594-7_60]

[20]   Kenichi Fujibayashi, Rizal Hariadi, Sung Ha Park, Erik Winfree, and Satoshi Murata: Toward reliable algorithmic self-assembly of DNA tiles: A fixed-width cellular automaton pattern. Nano Letters, 8(7):1791–1797, 2008. [doi:10.1021/nl0722830]

[21]   Michael R. Garey and David S. Johnson: Computers and Intractability. W. H. Freeman, New York, 1979.

[22]   Ming-Yang Kao and Robert T. Schweller: Reducing tile complexity for self-assembly through temperature programming. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 571–580. ACM Press, 2006. [doi:10.1145/1109557.1109620]

[23]   Ming-Yang Kao and Robert T. Schweller: Randomized self-assembly for approximate shapes. In Proc. 35th Internat. Colloq. on Automata, Languages and Programming (ICALP’08), pp. 370–384. Springer, 2008. [doi:10.1007/978-3-540-70575-8_31]

[24]   Ryan J. Kershner, Luisa D. Bozano, Christine M. Micheel, Albert M. Hung, Ann R. Fornof, Jennifer N. Cha, Charles T. Rettner, Marco Bersani, Jane Frommer, Paul W. K. Rothemund, and Gregory M. Wallraff: Placement and orientation of individual DNA shapes on lithographically patterned surfaces. Nature Nanotechnology, 3(9):557–561, 2009. [doi:10.1038/nnano.2009.220]

[25]   James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers: Computability and complexity in self-assembly. Theory of Computing Systems, 48(3):617–647, 2011. Preliminary version in CiE’08. [doi:10.1007/s00224-010-9252-0]

[26]   James I. Lathrop, Jack H. Lutz, and Scott M. Summers: Strict self-assembly of discrete Sierpinski triangles. Theoret. Comput. Sci., 410(4-5):384–405, 2009. Preliminary version in CiE’07. [doi:10.1016/j.tcs.2008.09.062]

[27]   Harry R. Lewis and Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, Inc., Upper Saddle River, New Jersey, 1998.

[28]   Dage Liu, Sung Ha Park, John H. Reif, and Thomas H. LaBean: DNA nanotubes self-assembled from triple-crossover tiles as templates for conductive nanowires. Proc. Nat. Acad. Sci., 101(3):717–722, 2004. [doi:10.1073/pnas.0305860101]

[29]   Kyle Lund, Anthony T. Manzo, Nadine Dabby, Nicole Micholotti, Alexander Johnson-Buck, Jeanetter Nangreave, Steven Taylor, Renjun Pei, Milan N. Stojanovic, Nils G. Walter, Erik Winfree, and Hao Yan: Molecular robots guided by prescriptive landscapes. Nature, 465(7295):206–210, 2010. [doi:10.1038/nature09012]

[30]   Stephen R. Mahaney: Sparse complete sets of NP: Solution of a conjecture of Berman and Hartmanis. J. Comput. System Sci., 25(2):130–143, 1982. Preliminary version in FOCS’80. [doi:10.1016/0022-0000(82)90002-2]

[31]   Ján Maňuch, Ladislav Stacho, and Christine Stoll: Two lower bounds for self-assemblies at temperature 1. J. Computational Biology, 17(6):841–852, 2010. Preliminary versions in SAC’09 and ICBBE’09. [doi:10.1089/cmb.2009.0067]

[32]   Ján Maňuch, Ladislav Stacho, and Christine Stoll: Step-wise tile assembly with a constant number of tile types. Natural Computing, 11(3):535–550, 2012. Preliminary version in ISAAC’09. [doi:10.1007/s11047-012-9321-1]

[33]   Hareem T. Maune, Si-Ping Han, Robert D. Barish, Marc Bockrath, William A. Goddard III, Paul W. K. Rothemund, and Erik Winfree: Self-assembly of carbon nanotubes into two-dimensional geometries using DNA origami templates. Nature Nanotechnology, 5(1):61–66, 2010. [doi:10.1038/nnano.2009.311]

[34]   Sung Ha Park, Constantin Pistol, Sang Jung Ahn, John H. Reif, Alvin R. Lebeck, Chris Dwyer, and Thomas H. LaBean: Finite-Size, Fully Addressable DNA Tile Lattices Formed by Hierarchical Assembly Procedures. Angewandte Chemie International Edition, 45(5):735–739, 2006. [doi:10.1002/anie.200503797]

[35]   Sung Ha Park, Hao Yan, John H. Reif, Thomas H. LaBean, and Gleb Finkelstein: Electronic Nanostructures Templated on Self-Assembled DNA Scaffolds. Nanotechnology, 15(10):S525–S527, 2004. [doi:10.1088/0957-4484/15/10/005]

[36]   Matthew J. Patitz: Simulation of self-assembly in the abstract tile assembly model with ISU TAS. In 6th Ann. Conf. Foundations of Nanoscience (FNANO’09), pp. 209–219. Sciencetechnica, 2009. [arXiv:1101.5151]

[37]   Paul W. K. Rothemund: Theory and Experiments in Algorithmic Self-Assembly. Ph. D. thesis, University of Southern California, 2001.

[38]   Paul W. K. Rothemund, Nick Papadakis, and Erik Winfree: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology, 2(12):2041–2053, 2004. [doi:10.1371/journal.pbio.0020424]

[39]   Paul W. K. Rothemund and Erik Winfree: The program-size complexity of self-assembled squares (extended abstract). In Proc. 32nd STOC, pp. 459–468. ACM Press, 2000. [doi:10.1145/335305.335358]

[40]   Marcus Schaefer and Christopher Umans: Completeness in the polynomial-time hierarchy: Part I: A compendium. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 33(3):32–49, 2002. [doi:10.1145/582475.582484]

[41]   Robert T. Schweller: Personal communication, 2011. http://faculty.utpa.edu/rtschweller/papers/TheGap.pdf.

[42]   Nadrian C. Seeman: Nucleic-acid junctions and lattices. Journal of Theoretical Biology, 99(2):237–247, 1982. [doi:10.1016/0022-5193(82)90002-9]

[43]   Shinnosuke Seki and Yasushi Okuno: On the behavior of tile assembly system at high temperatures. In 8th Conf. Computability in Europe, (CiE’12), pp. 549–559. Springer, 2012. [doi:10.1007/978-3-642-30870-3_55]

[44]   David Soloveichik and Erik Winfree: Complexity of self-assembled shapes. SIAM J. Comput., 36(6):1544–1569, 2007. Preliminary version in DNA’04. [doi:10.1137/S0097539704446712]

[45]   Larry J. Stockmeyer: The polynomial-time hierarchy. Theoret. Comput. Sci., 3(1):1–22, 1976. [doi:10.1016/0304-3975(76)90061-X]

[46]   Scott M. Summers: Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica, 63(1-2):117–136, 2012. [doi:10.1007/s00453-011-9522-5]

[47]   Hao Wang: Proving theorems by pattern recognition – II. The Bell System Technical Journal, XL(1):1–41, 1961.

[48]   Hao Wang: Dominoes and the AEA case of the decision problem. In Proc. Symp. Mathem. Theory of Automata (MTA’62), pp. 23–55. Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 1963.

[49]   Erik Winfree: Algorithmic Self-Assembly of DNA. Ph. D. thesis, California Institute of Technology, 1998.

[50]   Celia Wrathall: Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci., 3(1):23–33, 1976. [doi:10.1016/0304-3975(76)90062-1]

[51]   Hao Yan, Sung Ha Park, Gleb Finkelstein, John H. Reif, and Thomas H. LaBean: DNA-templated self-assembly of protein arrays and highly conductive nanowires. Science, 301(5641):1882–1884, 2003. [doi:10.1126/science.1089389]