2026-08-10T23:18:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14671 2024-03-06T10:54:35Z ddc:004 open_access

Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D Furcy, David Summers, Scott M. Withers, Logan Self-assembly algorithmic self-assembly tile self-assembly We investigate a fundamental question regarding a benchmark class of shapes in one of the simplest, yet most widely utilized abstract models of algorithmic tile self-assembly. More specifically, we study the directed tile complexity of a k × N thin rectangle in Winfree’s ubiquitous abstract Tile Assembly Model, assuming that cooperative binding cannot be enforced (temperature-1 self-assembly) and that tiles are allowed to be placed at most one step into the third dimension (just-barely 3D). While the directed tile complexities of a square and a scaled-up version of any algorithmically specified shape at temperature 1 in just-barely 3D are both asymptotically the same as they are (respectively) at temperature 2 in 2D, the (nearly tight) bounds on the directed tile complexity of a thin rectangle at temperature 2 in 2D are not currently known to hold at temperature 1 in just-barely 3D. Motivated by this discrepancy, we establish new lower and upper bounds on the directed tile complexity of a thin rectangle at temperature 1 in just-barely 3D. The proof of our upper bound is based on the construction of a novel, just-barely 3D temperature-1 self-assembling counter. Each value of the counter is comprised of k-2 digits, represented in a geometrically staggered fashion within k rows. This nearly optimal digit density, along with the base of the counter, which is proportional to N^{1/(k-1)}, results in an upper bound of O(N^{1/(k-1)} + log N), and is an asymptotic improvement over the previous state-of-the-art upper bound. On our way to proving our lower bound, we develop a new, more powerful type of specialized Window Movie Lemma that lets us bound the number of "sufficiently similar" ways to assign glues to a set (rather than a sequence) of fixed locations. Consequently, our lower bound, Ω(N^{1/k}), is also an asymptotic improvement over the previous state-of-the-art lower bound. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Furcy and Scott M. Summers and Logan Withers 2021 Is Part Of LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DNA.27.4 urn:nbn:de:0030-drops-146716 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.4 eng https://creativecommons.org/licenses/by/4.0/legalcode