Self-assembly of, and optimal encoding inside, thin rectangles at temperature-1 in 3D

In this paper, we study the self-assembly of rectangles in a non-cooperative, 3D version of Winfree's abstract Tile Assembly Model. We prove four main results -- the first two negative and the last two positive. First, we use Catalan numbers and a restricted version of the Window Movie Lemma (Meunier, Patitz, Summers, Theyssier, Winslow and Woods, SODA 2014) to prove two new lower bounds on the minimum number of unique tile types required for the self-assembly of rectangles. We then give a general construction for the efficient self-assembly of thin rectangles. Our construction is non-cooperative and"just-barely"3D in the sense that it places tiles at most one step into the third dimension. Finally, we give a non-cooperative, just-barely 3D optimal encoding construction that self-assembles the bits of a given binary string along the perimeter of a thin rectangle of constant height.

• Publication year

  2018

• Venue

  arXiv.org

• Publication date

  2018-08-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1808.04358
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimal Program-Size Complexity for Self-Assembled Squares at Temperature 1 in 3D

  2017influential reference
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation

  2017cited by this paper
• Optimal Self-Assembly of Finite Shapes at Temperature 1 in 3D

  2015cited by this paper
• Intrinsic universality in tile self-assembly requires cooperation

  2013cited by this paper
• Approximate Self-Assembly of the Sierpinski Triangle

  2010cited by this paper
• Limitations of self-assembly at temperature 1

  2009cited by this paper
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D

  2009cited by this paper
• Two Lower Bounds for Self-Assemblies at Temperature 1

  2009cited by this paper
• An information-bearing seed for nucleating algorithmic self-assembly

  2009cited by this paper
• Synthesis of crystals with a programmable kinetic barrier to nucleation

  2007cited by this paper
• Algorithmic Self-Assembly of DNA

  2006cited by this paper
• Complexity of Self-Assembled Shapes

  2004cited by this paper
• Algorithmic Self-Assembly of DNA Sierpinski Triangles

  2004cited by this paper
• Complexities for generalized models of self-assembly

  2004cited by this paper
• Running time and program size for self-assembled squares

  2001cited by this paper
• Logical computation using algorithmic self-assembly of DNA triple-crossover molecules

  2000cited by this paper
• The program-size complexity of self-assembled squares (extended abstract)

  2000cited by this paper
• Design and self-assembly of two-dimensional DNA crystals

  1998cited by this paper
• Concrete mathematics - a foundation for computer science (2. ed.)

  1994cited by this paper
• Concrete mathematics - a foundation for computer science

  1991cited by this paper
• Nucleic acid junctions and lattices.

  1982cited by this paper

• No citing papers are available for this paper.