EUVIMEDEUVIMED entdecken
Crossref

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

Furcy, David, Scott M. Summers

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 01.01.2026

DOI: 10.4230/lipics.dna.32.1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), erschienen am 01.01.2026. Verfasst von Furcy und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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).

Schlagwörter

tile self-assemblyabstract Tile Assembly Model

Zitieren

APA

Furcy, David, & Summers, S. M. (2026). Sequential Non-Determinism in Tile Self-Assembly: A General Framework and an Application to Efficient Temperature-1 Self-Assembly of Squares. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.dna.32.1

Vancouver

Furcy, David, Summers SM. Sequential Non-Determinism in Tile Self-Assembly: A General Framework and an Application to Efficient Temperature-1 Self-Assembly of Squares. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). 2026. doi:10.4230/lipics.dna.32.1

BibTeX
@article{Furcy2026,
  author = {Furcy and 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},
  journal = {DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)},
  year = {2026},
  doi = {10.4230/lipics.dna.32.1}
}
Kostenlos starten →