DROPS

Document

Sequential Non-Determinism in Tile Self-Assembly: A General Framework and an Application to Efficient Temperature-1 Self-Assembly of Squares

Authors: David Furcy and Scott M. Summers

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract

In this paper, we work in a 2D version of the probabilistic variant of Winfree’s abstract Tile Assembly Model defined by Chandran, Gopalkrishnan and Reif (SICOMP 2012) in which attaching tiles are sampled uniformly with replacement. First, we develop a framework called "sequential non-determinism" for analyzing the probabilistic correctness of a non-deterministic, temperature-1 tile assembly system (TAS) in which most (but not all) tile attachments are deterministic and the non-deterministic attachments always occur in a specific order. Our main sequential non-determinism result equates the probabilistic correctness of such a TAS to a finite product of probabilities, each of which (1) corresponds to the probability of the correct type of tile attaching at a point where it is possible for two different types to attach, and (2) ignores all other tile attachments that do not affect the non-deterministic attachment. We then show that sequential non-determinism allows for efficient and geometrically expressive self-assembly. To that end, we constructively prove that for any positive integer N and any real δ ∈ (0,1), there exists a TAS that self-assembles into an N × N square with probability at least 1 - δ using only O(log N + log 1/(δ)) types of tiles. Our bound improves upon the previous state-of-the-art bound for this problem by Cook, Fu and Schweller (SODA 2011).

Cite as

David Furcy and Scott M. Summers. Sequential Non-Determinism in Tile Self-Assembly: A General Framework and an Application to Efficient Temperature-1 Self-Assembly of Squares. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{furcy_et_al:LIPIcs.DNA.32.1,
  author =	{Furcy, David and Summers, Scott M.},
  title =	{{Sequential Non-Determinism in Tile Self-Assembly: A General Framework and an Application to Efficient Temperature-1 Self-Assembly of Squares}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.1},
  URN =		{urn:nbn:de:0030-drops-267710},
  doi =		{10.4230/LIPIcs.DNA.32.1},
  annote =	{Keywords: Self-assembly, tile assembly model, temperature 1, high probability self-assembly}
}

Document

DOI: 10.4230/LIPIcs.DNA.27.4

Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D

Authors: David Furcy, Scott M. Summers, and Logan Withers

Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)

Abstract

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.

Cite as

David Furcy, Scott M. Summers, and Logan Withers. Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{furcy_et_al:LIPIcs.DNA.27.4,
  author =	{Furcy, David and Summers, Scott M. and Withers, Logan},
  title =	{{Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.4},
  URN =		{urn:nbn:de:0030-drops-146716},
  doi =		{10.4230/LIPIcs.DNA.27.4},
  annote =	{Keywords: Self-assembly, algorithmic self-assembly, tile self-assembly}
}

Search Results

Documents authored by Furcy, David

Sequential Non-Determinism in Tile Self-Assembly: A General Framework and an Application to Efficient Temperature-1 Self-Assembly of Squares

Abstract

Cite as

Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D

Abstract

Cite as

Thanks for your feedback!

Could not send message