Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D
Ist Teil von
Theory of computing systems, 2023-10, Vol.67 (5), p.1082-1130
Ort / Verlag
New York: Springer US
Erscheinungsjahr
2023
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
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 on the directed tile complexity of a thin rectangle at temperature 1 in just-barely 3D of
O
N
1
k
-
1
+
k
, 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 on the directed tile complexity of a thin rectangle at temperature 1 in just-barely 3D of
Ω
N
1
k
, is also an asymptotic improvement over the previous state-of-the-art lower bound.