25 Search Results for "Winfree, Erik"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.7
Polynomial Equivalence of Extended Chemical Reaction Models

Authors: Divya Bajaj, Jose-Luis Castellanos, Ryan Knobel, Austin Luchsinger, Aiden Massie, Adrian Salinas, Pablo Santos, Ramiro Santos, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The ability to detect whether a species (or dimension) is zero in Chemical Reaction Networks (CRN), Vector Addition Systems, or Petri Nets is known to increase the power of these models - making them capable of universal computation. While this ability may appear in many forms, such as extending the models to allow transitions to be inhibited, prioritized, or synchronized, we present an extension that directly performs this zero checking. We introduce a new void genesis CRN variant with a simple design that merely increments the count of a specific species when any other species' count goes to zero. As with previous extensions, we show that the model is Turing Universal. We then analyze several other studied CRN variants and show that they are all equivalent through a polynomial simulation with the void genesis model, which does not merely follow from Turing-universality. Thus, inhibitor species, reactions that occur at different rates, being allowed to run reactions in parallel, or even being allowed to continually add more volume to the CRN, does not add additional simulation power beyond simply detecting if a species count becomes zero.
Cite as

Divya Bajaj, Jose-Luis Castellanos, Ryan Knobel, Austin Luchsinger, Aiden Massie, Adrian Salinas, Pablo Santos, Ramiro Santos, Robert Schweller, and Tim Wylie. Polynomial Equivalence of Extended Chemical Reaction Models. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bajaj_et_al:LIPIcs.ISAAC.2025.7,
  author =	{Bajaj, Divya and Castellanos, Jose-Luis and Knobel, Ryan and Luchsinger, Austin and Massie, Aiden and Salinas, Adrian and Santos, Pablo and Santos, Ramiro and Schweller, Robert and Wylie, Tim},
  title =	{{Polynomial Equivalence of Extended Chemical Reaction Models}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.7},
  URN =		{urn:nbn:de:0030-drops-249158},
  doi =		{10.4230/LIPIcs.ISAAC.2025.7},
  annote =	{Keywords: Chemical Reaction Networks, Simulations, Petri-nets, Vector Addition Systems, Bi-simulation, Turing-universality, Inhibitors}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.11
Universality Frontier for Asynchronous Cellular Automata

Authors: Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, and Roger Wattenhofer

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In this work, we investigate computational aspects of asynchronous cellular automata (ACAs), a modification of cellular automata in which cells update independently, following an asynchronous update schedule. We introduce flip automata networks (FANs), a simple modification of automata networks that remain robust under any asynchronous updating order. By using FANs as a middleman, we show that asynchronous automata can efficiently simulate their synchronous counterparts with a linear memory overhead, which improves upon the previously established quadratic bound. Additionally, we address the universality gap for (a)synchronous cellular automata-the boundary separating universal and non-universal automata, which is still not fully understood. We tighten this boundary by proving that all one-way asynchronous automata lack universal computational power. Conversely, we establish the existence of a universal asynchronous 6-state first-neighbor automaton in one dimension and a 3-state von Neumann automaton in two dimensions, which represent the smallest known universal constructions to date.
Cite as

Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, and Roger Wattenhofer. Universality Frontier for Asynchronous Cellular Automata. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baburin_et_al:LIPIcs.MFCS.2025.11,
  author =	{Baburin, Ivan and Cook, Matthew and Gr\"{o}tschla, Florian and Plesner, Andreas and Wattenhofer, Roger},
  title =	{{Universality Frontier for Asynchronous Cellular Automata}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.11},
  URN =		{urn:nbn:de:0030-drops-241182},
  doi =		{10.4230/LIPIcs.MFCS.2025.11},
  annote =	{Keywords: Universality, Asynchronous Cellular Automata, Automata Networks}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.1
Algorithmic Hardness of the Partition Function for Nucleic Acid Strands

Authors: Gwendal Ducloz, Ahmed Shalaby, and Damien Woods

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
To understand and engineer biological and artificial nucleic acid systems, algorithms are employed for prediction of secondary structures at thermodynamic equilibrium. Dynamic programming algorithms are used to compute the most favoured, or Minimum Free Energy (MFE), structure, and the Partition Function (PF) - a tool for assigning a probability to any structure. However, in some situations, such as when there are large numbers of strands, or pseudoknotted systems, NP-hardness results show that such algorithms are unlikely, but only for MFE. Curiously, algorithmic hardness results were not shown for PF, leaving two open questions on the complexity of PF for multiple strands and single strands with pseudoknots. The challenge is that while the MFE problem cares only about one, or a few structures, PF is a summation over the entire secondary structure space, giving theorists the vibe that computing PF should not only be as hard as MFE, but should be even harder. We answer both questions. First, we show that computing PF is #P-hard for systems with an unbounded number of strands, answering a question of Condon Hajiaghayi, and Thachuk [DNA27]. Second, for even a single strand, but allowing pseudoknots, we find that PF is #P-hard. Our proof relies on a novel magnification trick that leads to a tightly-woven set of reductions between five key thermodynamic problems: MFE, PF, their decision versions, and #SSEL that counts structures of a given energy. Our reductions show these five problems are fundamentally related for any energy model amenable to magnification. That general classification clarifies the mathematical landscape of nucleic acid energy models and yields several open questions.
Cite as

Gwendal Ducloz, Ahmed Shalaby, and Damien Woods. Algorithmic Hardness of the Partition Function for Nucleic Acid Strands. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ducloz_et_al:LIPIcs.DNA.31.1,
  author =	{Ducloz, Gwendal and Shalaby, Ahmed and Woods, Damien},
  title =	{{Algorithmic Hardness of the Partition Function for Nucleic Acid Strands}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.1},
  URN =		{urn:nbn:de:0030-drops-238504},
  doi =		{10.4230/LIPIcs.DNA.31.1},
  annote =	{Keywords: Partition function, minimum free energy, nucleic acid, DNA, RNA, secondary structure, computational complexity, #P-hardness}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.2
A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs

Authors: Hope Amber Johnson and Anne Condon

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
DNA strand displacement, a collective name for certain behaviors of short strands of DNA, has been used to build many interesting molecular devices over the past few decades. Among those devices are general implementation schemes for Chemical Reaction Networks, suggesting a place in an abstraction hierarchy for complex molecular programming. However, the possibilities of DNA strand displacement are far from fully explored. On a theoretical level, most DNA strand displacement systems are built out of a few simple motifs, with the space of possible motifs otherwise unexplored. On a practical level, the desire for general, large-scale DNA strand displacement systems is not fulfilled. Those systems that are scalable are not general, and those that are general don't scale up well. We have recently been exploring the space of possibilities for DNA strand displacement systems where all input complexes are made out of at most two strands of DNA. As a test case, we've had an open question of whether such systems can implement general Chemical Reaction Networks, in a way that has a certain set of other desirable properties - reversible, systematic, O(1) toeholds, bimolecular reactions, and correct according to CRN bisimulation - that the state-of-the-art implementations with more than 2-stranded inputs have. Until now we've had a few results that have all but one of those desirable properties, including one based on a novel mechanism we called coupled reconfiguration, but that depended on the physically questionable assumption that pseudoknots cannot occur. We wondered whether the same type of mechanism could be done in a pseudoknot-robust way. In this work we show that in fact, coupled reconfiguration can be done in a pseudoknot-robust way, and this mechanism can implement general Chemical Reaction Networks with all inputs being single strands of DNA. Going further, the same motifs used in this mechanism can implement stacks and surface-based bimolecular reactions. Those have been previously studied as part of polymer extensions of the Chemical Reaction Network model, and on an abstract model level, the resulting extensions are Turing-complete in ways the base Chemical Reaction Network model is not. Our mechanisms are significantly different from previously tested DNA strand displacement systems, which raises questions about their ability to be implemented experimentally, but we have some reasons to believe the challenges are solvable. So we present the pseudoknot-robust coupled reconfiguration mechanism and its use for general Chemical Reaction Network implementations; we present the extensions of the mechanism to stack and surface reactions; and we discuss the possible obstacles and solutions to experimental implementation, as well as the theoretical implications of this mechanism.
Cite as

Hope Amber Johnson and Anne Condon. A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.DNA.31.2,
  author =	{Johnson, Hope Amber and Condon, Anne},
  title =	{{A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.2},
  URN =		{urn:nbn:de:0030-drops-238514},
  doi =		{10.4230/LIPIcs.DNA.31.2},
  annote =	{Keywords: Molecular programming, DNA strand displacement, Chemical Reaction Networks}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.3
Reachability in Deletion-Only Chemical Reaction Networks

Authors: Bin Fu, Timothy Gomez, Ryan Knobel, Austin Luchsinger, Aiden Massie, Marco Rodriguez, Adrian Salinas, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
For general discrete Chemical Reaction Networks (CRNs), the fundamental problem of reachability - the question of whether a target configuration can be produced from a given initial configuration - was recently shown to be Ackermann-complete. However, many open questions remain about which features of the CRN model drive this complexity. We study a restricted class of CRNs with void rules, reactions that only decrease species counts. We further examine this regime in the motivated model of step CRNs, which allow additional species to be introduced in discrete stages. With and without steps, we characterize the complexity of the reachability problem for CRNs with void rules. We show that, without steps, reachability remains polynomial-time solvable for bimolecular systems but becomes NP-complete for larger reactions. Conversely, with just a single step, reachability becomes NP-complete even for bimolecular systems. Our results provide a nearly complete classification of void-rule reachability problems into tractable and intractable cases, with only a single exception.
Cite as

Bin Fu, Timothy Gomez, Ryan Knobel, Austin Luchsinger, Aiden Massie, Marco Rodriguez, Adrian Salinas, Robert Schweller, and Tim Wylie. Reachability in Deletion-Only Chemical Reaction Networks. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.DNA.31.3,
  author =	{Fu, Bin and Gomez, Timothy and Knobel, Ryan and Luchsinger, Austin and Massie, Aiden and Rodriguez, Marco and Salinas, Adrian and Schweller, Robert and Wylie, Tim},
  title =	{{Reachability in Deletion-Only Chemical Reaction Networks}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.3},
  URN =		{urn:nbn:de:0030-drops-238521},
  doi =		{10.4230/LIPIcs.DNA.31.3},
  annote =	{Keywords: CRN, Chemical Reaction Network, Reachability, Void Reactions}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.4
Differentiable Programming of Indexed Chemical Reaction Networks and Reaction-Diffusion Systems

Authors: Inhoo Lee, Salvador Buse, and Erik Winfree

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
Many molecular systems are best understood in terms of prototypical species and reactions. The central dogma and related biochemistry are rife with examples: gene i is transcribed into RNA i, which is translated into protein i; kinase n phosphorylates substrate m; protein p dimerizes with protein q. Engineered nucleic acid systems also often have this form: oligonucleotide i hybridizes to complementary oligonucleotide j; signal strand n displaces the output of seesaw gate m; hairpin p triggers the opening of target q. When there are many variants of a small number of prototypes, it can be conceptually cleaner and computationally more efficient to represent the full system in terms of indexed species (e.g. for dimerization, M_p, D_pq) and indexed reactions (M_p + M_q → D_pq). Here, we formalize the Indexed Chemical Reaction Network (ICRN) model and describe a Python software package designed to simulate such systems in the well-mixed and reaction-diffusion settings, using a differentiable programming framework originally developed for large-scale neural network models, taking advantage of GPU acceleration when available. Notably, this framework makes it straightforward to train the models’ initial conditions and rate constants to optimize a target behavior, such as matching experimental data, performing a computation, or exhibiting spatial pattern formation. The natural map of indexed chemical reaction networks onto neural network formalisms provides a tangible yet general perspective for translating concepts and techniques from the theory and practice of neural computation into the design of biomolecular systems.
Cite as

Inhoo Lee, Salvador Buse, and Erik Winfree. Differentiable Programming of Indexed Chemical Reaction Networks and Reaction-Diffusion Systems. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.DNA.31.4,
  author =	{Lee, Inhoo and Buse, Salvador and Winfree, Erik},
  title =	{{Differentiable Programming of Indexed Chemical Reaction Networks and Reaction-Diffusion Systems}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.4},
  URN =		{urn:nbn:de:0030-drops-238534},
  doi =		{10.4230/LIPIcs.DNA.31.4},
  annote =	{Keywords: Differentiable Programming, Chemical Reaction Networks, Reaction-Diffusion Systems}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.7
Tile Blockers as a Simple Motif to Control Self-Assembly: Kinetics and Thermodynamics

Authors: Constantine G. Evans, Angel Cervera Roldan, Trent Rogers, and Damien Woods

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
A fundamental problem in crystallisation, and in molecular tile-based self-assembly in particular, is how to simultaneously control its two main constituent processes: seeded growth and spontaneous nucleation. Often, we desire out-of-equilibrium growth without spontaneous nucleation, which can be achieved through careful calibration of temperature, concentration and experimental time-scale a laborious and overly-sensitive approach. Another technique is to find alternative nucleation-resistant tile designs [Minev et al, 2001]. Rogers, Evans and Woods [In prep] propose blockers: short DNA strands designed to dynamically block DNA tile sides, altering self-assembly dynamics. Experiments showed independent and tunable control on nucleation and growth rates. Here, we provide a theoretical explanation for these surprising results. We formally define the kBlock model where blockers bind to tiles at thermodynamic equilibrium in solution and stochastic kinetics allow self-assembly of a tiled structure. In an intentionally simplified mathematical setting we show that blockers permit reasonable seeded growth rates, akin to a non-blocked tile system at lower tile concentration, crucially giving nucleation rates that are exponentially suppressed. We then implement the kBlock model in a stochastic simulator, with results showing remarkable alignment with oversimplified theory. We provide evidence of blocker-induced tile buffering, where a large reservoir of blocked tiles slowly feeds a small unblocked tile subpopulation which acts like a regular, non-blocked, low tile concentration system, yet is capable of long-term buffered assembly. Finally, and perhaps most satisfyingly, theory and simulations align remarkably well with DNA self-assembly experiments over a wide range of concentrations and temperatures, matching the size of growth temperature windows to within 12%. Blockers are a straightforward solution to the challenging problem of simultaneously and independently controlling growth and nucleation, using a motif compatible with many DNA tile systems.
Cite as

Constantine G. Evans, Angel Cervera Roldan, Trent Rogers, and Damien Woods. Tile Blockers as a Simple Motif to Control Self-Assembly: Kinetics and Thermodynamics. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{evans_et_al:LIPIcs.DNA.31.7,
  author =	{Evans, Constantine G. and Cervera Roldan, Angel and Rogers, Trent and Woods, Damien},
  title =	{{Tile Blockers as a Simple Motif to Control Self-Assembly: Kinetics and Thermodynamics}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.7},
  URN =		{urn:nbn:de:0030-drops-238564},
  doi =		{10.4230/LIPIcs.DNA.31.7},
  annote =	{Keywords: Self-assembly, kinetic model, kinetic simulation, thermodynamic prediction}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.8
An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming

Authors: Matthew J. Patitz and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we present a theoretical design for tile-based self-assembling systems where individual tile sets that are universal for various tasks (e.g. building shapes or encoding arbitrary data for algorithmic systems) can be provided their input solely using sequences of variations in temperatures. Although there is prior theoretical work in so-called "temperature programming," the results presented here are based upon recent experimental work with "blocked tiles" that provides plausible evidence for their practical implementation. We develop and present an abstract mathematical model, the BlockTAM, for such systems that is based upon the experimental work, and provide constructions within it for universal number encoding systems and a universal shape building construction. These results mirror previous results in temperature programming, covering the two ends of the spectrum that seek to balance the scale factors of assemblies with the number of temperature phases required, while leveraging the features of the BlockTAM that we hope provide a pathway for future experimental implementations.
Cite as

Matthew J. Patitz and Trent A. Rogers. An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{patitz_et_al:LIPIcs.DNA.31.8,
  author =	{Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.8},
  URN =		{urn:nbn:de:0030-drops-238574},
  doi =		{10.4230/LIPIcs.DNA.31.8},
  annote =	{Keywords: DNA tiles, self-assembly, temperature programming}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.9
Synchronous Versus Asynchronous Tile-Based Self-Assembly

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we study the relationship between mathematical models of tile-based self-assembly which differ in terms of the synchronicity of tile additions. In the standard abstract Tile Assembly Model (aTAM), each step of assembly consists of a single tile being added to an assembly. At any given time, each location on the perimeter of an assembly to which a tile can legally bind is called a frontier location, and for each step of assembly one frontier location is randomly selected and a tile is added. In the Synchronous Tile Assembly Model (syncTAM), at each step of assembly every frontier location simultaneously receives a tile. Our results show that while directed, non-cooperative syncTAM systems are capable of universal computation (while directed, non-cooperative aTAM systems are known not to be), and they are capable of building shapes that can't be built within the aTAM, the non-cooperative aTAM is also capable of building shapes that can't be built within the syncTAM even cooperatively. We show a variety of results that demonstrate the similarities and differences between these two models.
Cite as

Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers. Synchronous Versus Asynchronous Tile-Based Self-Assembly. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.31.9,
  author =	{Becker, Florent and Drake, Phillip and Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{Synchronous Versus Asynchronous Tile-Based Self-Assembly}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.9},
  URN =		{urn:nbn:de:0030-drops-238580},
  doi =		{10.4230/LIPIcs.DNA.31.9},
  annote =	{Keywords: self-assembly, noncooperative self-assembly, models of computation, tile assembly systems}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.10
Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems

Authors: Hamidreza Akef, Minki Hhan, and David Soloveichik

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
Computing equilibrium concentrations of molecular complexes is generally analytically intractable and requires numerical approaches. In this work we focus on the polymer-monomer level, where indivisible molecules (monomers) combine to form complexes (polymers). Rather than employing free-energy parameters for each polymer, we focus on the athermic setting where all interactions preserve enthalpy. This setting aligns with the strongly bonded (domain-based) regime in DNA nanotechnology when strands can bind in different ways, but always with maximum overall bonding - and is consistent with the saturated configurations in the Thermodynamic Binding Networks (TBNs) model. Within this context, we develop an iterative algorithm for assigning polymer concentrations to satisfy detailed-balance, where on-target (desired) polymers are in high concentrations and off-target (undesired) polymers are in low. Even if not directly executed, our algorithm provides effective insights into upper bounds on concentration of off-target polymers, connecting combinatorial arguments about discrete configurations such as those in the TBN model to real-valued concentrations. We conclude with an application of our method to decreasing leak in DNA logic and signal propagation. Our results offer a new framework for design and verification of equilibrium concentrations when configurations are distinguished by entropic forces.
Cite as

Hamidreza Akef, Minki Hhan, and David Soloveichik. Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akef_et_al:LIPIcs.DNA.31.10,
  author =	{Akef, Hamidreza and Hhan, Minki and Soloveichik, David},
  title =	{{Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.10},
  URN =		{urn:nbn:de:0030-drops-238595},
  doi =		{10.4230/LIPIcs.DNA.31.10},
  annote =	{Keywords: Equilibrium concentrations, Thermodynamic Binding Networks, Monomer-polymer model, Detailed balance}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.11
Leakless Polymerase-Dependent Strand Displacement Systems

Authors: Zoë Evelyn Mōhalakealoha Derauf and Chris Thachuk

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
A grand challenge facing molecular programmers is the rational development of fast, robust, and isothermal architectures akin to "chemical central processing units" that can sense (bio-)chemical signals from their environment, perform complex computation, and orchestrate a physical response in situ. DNA strand displacement systems (DSDs) remain a compelling candidate, but are hampered by spurious reaction pathways that lead to incorrect output. DSDs that utilize the systematic leakless motif can be made arbitrarily robust at the cost of increasing redundancy and network size (scaling), and thus a degradation of kinetic performance. Another class of architectures utilize DNA hybridization, extension, and signal production of entirely sequestered outputs via strand-displacing polymerases (SDPs) that have resulted in impressive demonstrations; however, they face similar challenges of aberrant behavior such as mis-priming by incorrect signals. Our work introduces a unified polymerase-dependent toehold-mediated strand displacement (PD-TMSD) architecture that integrates the programmed specificity of DSDs with the unique advantages of SDPs. This unification enables systems that can be made arbitrarily robust, at any concentration range, without increasing network size. We propose a number of gate designs and composition rules to compute arbitrary Boolean functions, emulate arbitrary chemical reaction networks, and explore time-bounded probabilistic computation made possible by certain classes of SDPs. Our theoretical exploration is backed by preliminary experimental demonstrations. This contribution was inspired by the belief that molecular programming can meet or exceed the complexity exhibited in biology if we embrace its best understood molecular machinery and couple it with systematic design principles built upon a strong theoretical foundation.
Cite as

Zoë Evelyn Mōhalakealoha Derauf and Chris Thachuk. Leakless Polymerase-Dependent Strand Displacement Systems. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derauf_et_al:LIPIcs.DNA.31.11,
  author =	{Derauf, Zo\"{e} Evelyn M\={o}halakealoha and Thachuk, Chris},
  title =	{{Leakless Polymerase-Dependent Strand Displacement Systems}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.11},
  URN =		{urn:nbn:de:0030-drops-238608},
  doi =		{10.4230/LIPIcs.DNA.31.11},
  annote =	{Keywords: DNA strand displacement, strand-displacing polymerases, molecular computation, energy barriers, kinetics}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.130
An Efficient Algorithm to Compute the Minimum Free Energy of Interacting Nucleic Acid Strands

Authors: Ahmed Shalaby and Damien Woods

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The information-encoding molecules RNA and DNA bind via base pairing to form an exponentially large set of secondary structures. Practitioners need algorithms to predict the most favoured structures, called minimum free energy (MFE) structures, or to compute a partition function that allows assigning a probability to any structure. MFE prediction is NP-hard in the presence pseudoknots - base pairings that violate a restricted planarity condition. However, for single-stranded unpseudoknotted structures, there are polynomial time dynamic programming algorithms. For multiple strands, the problem is significantly more complicated: Codon, Hajiaghayi and Thachuk [DNA27, 2021] proved it NP-hard for N bases and 𝒪(N) strands. Dirks, Bois, Schaeffer, Winfree and Pierce [SIAM Review, 2007] gave a polynomial time partition function algorithm for multiple (𝒪(1)) strands, now widely-used, however their technique did not generalise to MFE which they left open. We give an 𝒪(N⁴) time algorithm for unpseudoknotted multiple (𝒪(1)) strand MFE prediction, answering the open problem from Dirks et al. The challenge lies in considering the rotational symmetry of secondary structures, a global feature not immediately amenable to local subproblem decomposition used in dynamic programming. Our proof has two main technical contributions: First, a characterisation of symmetric secondary structures implying only quadratically many need to be considered when computing the rotational symmetry penalty. Second, that bound is leveraged by a backtracking algorithm to efficiently find the MFE in an exponential space of contenders.
Cite as

Ahmed Shalaby and Damien Woods. An Efficient Algorithm to Compute the Minimum Free Energy of Interacting Nucleic Acid Strands. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 130:1-130:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shalaby_et_al:LIPIcs.ICALP.2025.130,
  author =	{Shalaby, Ahmed and Woods, Damien},
  title =	{{An Efficient Algorithm to Compute the Minimum Free Energy of Interacting Nucleic Acid Strands}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{130:1--130:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.130},
  URN =		{urn:nbn:de:0030-drops-235071},
  doi =		{10.4230/LIPIcs.ICALP.2025.130},
  annote =	{Keywords: Minimum free energy, MFE, partition function, nucleic acid, DNA, RNA, secondary structure, computational complexity, algorithm analysis and design, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.1
The Expressive Power of Uniform Population Protocols with Logarithmic Space

Authors: Philipp Czerner, Vincent Fischer, and Roland Guttenberg

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
Population protocols are a model of computation in which indistinguishable mobile agents interact in pairs to decide a property of their initial configuration. Originally introduced by Angluin et. al. in 2004 with a constant number of states, research nowadays focuses on protocols where the space usage depends on the number of agents. The expressive power of population protocols has so far however only been determined for protocols using o(log n) states, which compute only semilinear predicates, and for Ω(n) states. This leaves a significant gap, particularly concerning protocols with Θ(log n) or Θ(polylog n) states, which are the most common constructions in the literature. In this paper we close the gap and prove that for any ε > 0 and f ∈ Ω(log n)∩𝒪(n^{1-ε}), both uniform and non-uniform population protocols with Θ(f(n)) states can decide exactly those predicates, whose unary encoding lies in NSPACE(f(n) log n).
Cite as

Philipp Czerner, Vincent Fischer, and Roland Guttenberg. The Expressive Power of Uniform Population Protocols with Logarithmic Space. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{czerner_et_al:LIPIcs.SAND.2025.1,
  author =	{Czerner, Philipp and Fischer, Vincent and Guttenberg, Roland},
  title =	{{The Expressive Power of Uniform Population Protocols with Logarithmic Space}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.1},
  URN =		{urn:nbn:de:0030-drops-230540},
  doi =		{10.4230/LIPIcs.SAND.2025.1},
  annote =	{Keywords: Population Protocols, Uniform, Expressive Power}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.11
Hardness of Traversing Gadget Systems with Small Bandwidth

Authors: MIT Gadgets Group, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, and Jayson Lynch

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
The motion-planning-through-gadgets framework has enabled proofs of PSPACE-completeness for many motion-planning problems, ranging from swarm and modular robotics to DNA computing to video games. In this paper, we strengthen this framework to show that, for several useful gadgets and gadget families, motion planning remains PSPACE-complete even when gadgets are connected together into a graph of constant bandwidth (which implies constant pathwidth, treewidth, and cliquewidth). We then show how this result applies to several geometric/grid-based motion-planning problems, establishing PSPACE-completeness even when restricted to a rectangle/box where only one dimension is large (superconstant). On the positive side, we find one family of gadgets (DAG gadgets) for which motion planning is fixed-parameter tractable with respect to bandwidth.
Cite as

MIT Gadgets Group, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, and Jayson Lynch. Hardness of Traversing Gadget Systems with Small Bandwidth. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mitgadgetsgroup_et_al:LIPIcs.SAND.2025.11,
  author =	{MIT Gadgets Group and Demaine, Erik D. and Diomidova, Jenny and Gomez, Timothy and Hecher, Markus and Lynch, Jayson},
  title =	{{Hardness of Traversing Gadget Systems with Small Bandwidth}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.11},
  URN =		{urn:nbn:de:0030-drops-230648},
  doi =		{10.4230/LIPIcs.SAND.2025.11},
  annote =	{Keywords: Gadgets, Motion Planning, Parameterized Complexity, Hardness}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.14
Fractals in Seeded Tile Automata

Authors: Asher Haun, Ryan Knobel, Adrian Salinas, Ramiro Santos, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
This work fully characterizes fractal generation in the seeded Tile Automata model (seeded TA), a model similar to the abstract Tile Assembly model (aTAM) with the added ability for adjacent tiles to change states. Under these assumptions, we first show that all discrete self-similar fractals (DSSFs) with feasible generators are strictly buildable at scale 1 and temperature 1 in seeded TA. We then show that these results imply the existence of a single seeded TA system Γ that can strictly build any DSSF infinitely at scale 1 and temperature 1.
Cite as

Asher Haun, Ryan Knobel, Adrian Salinas, Ramiro Santos, Robert Schweller, and Tim Wylie. Fractals in Seeded Tile Automata. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haun_et_al:LIPIcs.SAND.2025.14,
  author =	{Haun, Asher and Knobel, Ryan and Salinas, Adrian and Santos, Ramiro and Schweller, Robert and Wylie, Tim},
  title =	{{Fractals in Seeded Tile Automata}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.14},
  URN =		{urn:nbn:de:0030-drops-230677},
  doi =		{10.4230/LIPIcs.SAND.2025.14},
  annote =	{Keywords: self-assembly, tile automata, fractals}
}
  • Refine by Type
  • 25 Document/PDF
  • 19 Document/HTML

  • Refine by Publication Year
  • 19 2025
  • 1 2024
  • 2 2023
  • 1 2021
  • 2 2020

  • Refine by Author
  • 5 Knobel, Ryan
  • 5 Schweller, Robert
  • 5 Wylie, Tim
  • 4 Salinas, Adrian
  • 4 Woods, Damien
  • Show More...

  • Refine by Series/Journal
  • 25 LIPIcs

  • Refine by Classification
  • 10 Theory of computation → Models of computation
  • 5 Applied computing → Chemistry
  • 5 Theory of computation → Problems, reductions and completeness
  • 3 Computer systems organization → Molecular computing
  • 3 Theory of computation → Distributed computing models
  • Show More...

  • Refine by Keyword
  • 4 Chemical Reaction Networks
  • 4 DNA strand displacement
  • 3 self-assembly
  • 2 CRN
  • 2 Chemical Reaction Network
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact