DROPS

Document

Powers and Limitations of Synchronous Self-Assembly: Non-cooperative Assemblies and Limited Synchronization

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, and Ryder Smith

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

Abstract

In abstract models of algorithmic self-assembly, synchronization between attachments has emerged as a crucial distinction between the classical asynchronous model (aTAM) and a new synchronous model, the syncTAM. This paper presents recent advances in gauging the additional power afforded by the syncTAM. While it is known that the syncTAM and the aTAM are each unable to fully simulate the other, this paper offers evidence that the syncTAM is computationally significantly more powerful than the aTAM, especially in the non-cooperative setting. The additional power of the non-cooperative syncTAM is witnessed by the following constructions, all impossible in the non-cooperative aTAM: a flagpole, a strict self-assembly of a variant of the discrete Sierpinski triangle, and the ability to build the same assemblies (modulo scale factor) as directed aTAM systems. The second topic is that of limited synchronization, wherein, when the number of attachments is smaller than some threshold l, they happen synchronously, but attachments in excess of that number must wait. In that context, the precise value of l is crucial, and changes to that value prevent simulation and can change which shapes can be obtained.

Cite as

Florent Becker, Phillip Drake, Matthew J. Patitz, and Ryder Smith. Powers and Limitations of Synchronous Self-Assembly: Non-cooperative Assemblies and Limited Synchronization. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.32.2,
  author =	{Becker, Florent and Drake, Phillip and Patitz, Matthew J. and Smith, Ryder},
  title =	{{Powers and Limitations of Synchronous Self-Assembly: Non-cooperative Assemblies and Limited Synchronization}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{2:1--2:23},
  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.2},
  URN =		{urn:nbn:de:0030-drops-267728},
  doi =		{10.4230/LIPIcs.DNA.32.2},
  annote =	{Keywords: self-assembly, noncooperative self-assembly, models of computation, tile assembly systems}
}

Search Results

Documents authored by Smith, Ryder

Powers and Limitations of Synchronous Self-Assembly: Non-cooperative Assemblies and Limited Synchronization

Abstract

Cite as

Thanks for your feedback!

Could not send message