24 Search Results for "Woods, Damien"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.14
General Computation Using Slidable Tiles with Deterministic Global Forces

Authors: Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the computational power of the Full-Tilt model of motion planning, where slidable polyominos are moved maximally around a board by way of a sequence of directional "tilts." We focus on the deterministic scenario in which the tilts constitute a repeated clockwise rotation. We show that general-purpose computation is possible within this framework by providing a direct and efficient simulation of space-bounded Turing machines in which one computational step of the machine is simulated per O(1) rotations. We further show that the initial tape of the machine can be programmed by an initial tilt-sequence preceding the rotations. This result immediately implies new PSPACE-completeness results for the well-studied problems of occupancy (deciding if a given board location can be occupied by a tile), vacancy (deciding if a location can be emptied), relocation (deciding if a tile can be moved from one location to another), and reconfiguration (can a given board configuration be reconfigured into a second given configuration) that hold even for deterministically repeating tilt cycles such as rotations. All of our PSPACE-completeness results hold even when there is only a single domino in the system beyond singleton tiles. Following, we show that these results work in the Single-Step tilt model for larger constant cycles. We then investigate computational efficiency by showing a modification to implement a two-tape Turing machine in the Full-Tilt model and Systolic Arrays in the Single-Step model. Finally, we show a cyclic implementation for tilt-efficient Threshold Circuits.
Cite as

Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie. General Computation Using Slidable Tiles with Deterministic Global Forces. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{avilajimenez_et_al:LIPIcs.ITCS.2026.14,
  author =	{Avila-Jimenez, Alberto and Barreda, David and Evans, Sarah-Laurie and Luchsinger, Austin and Massie, Aiden and Schweller, Robert and Tomai, Evan and Wylie, Tim},
  title =	{{General Computation Using Slidable Tiles with Deterministic Global Forces}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.14},
  URN =		{urn:nbn:de:0030-drops-253019},
  doi =		{10.4230/LIPIcs.ITCS.2026.14},
  annote =	{Keywords: motion planning, global control, external forces, deterministic computation, occupancy, vacancy}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.7
Unbound Human-Machine Interfaces for Interaction in Weightless Environments

Authors: Jessica R. Cauchard

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
User interfaces are subject to the rules of physics (e.g., Newton and Archimedes' laws) relevant to the environment they are in. As such, most interfaces and interaction techniques have been designed for Earth surface. However, when interacting with technology in weightless environments, such as in space, both human and machine will be subject to different physical constraints. For instance, underwater or in Space, people can experience spatial disorientation, which will in turn affect how they use a system. This position paper conceptualizes unbound Human-Machine Interfaces (HMIs) as interfaces where either, or both, human and machine are located beyond Earth surface. In particular, it describes how traditional HCI needs to be rethought for interaction in weightless environments and how theoretical models such as joint cognition can support future developments of unbound interfaces.
Cite as

Jessica R. Cauchard. Unbound Human-Machine Interfaces for Interaction in Weightless Environments. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 7:1-7:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cauchard:OASIcs.SpaceCHI.2025.7,
  author =	{Cauchard, Jessica R.},
  title =	{{Unbound Human-Machine Interfaces for Interaction in Weightless Environments}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{7:1--7:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.7},
  URN =		{urn:nbn:de:0030-drops-239970},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.7},
  annote =	{Keywords: human-robot interaction, gravity, space, interaction technique}
}
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.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
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.SoCG.2025.39
Tiling with Three Polygons Is Undecidable

Authors: Erik D. Demaine and Stefan Langerman

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of the three polygons (either allowing or forbidding reflections)? This result improves on the best previous construction which requires five polygons.
Cite as

Erik D. Demaine and Stefan Langerman. Tiling with Three Polygons Is Undecidable. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.SoCG.2025.39,
  author =	{Demaine, Erik D. and Langerman, Stefan},
  title =	{{Tiling with Three Polygons Is Undecidable}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.39},
  URN =		{urn:nbn:de:0030-drops-231913},
  doi =		{10.4230/LIPIcs.SoCG.2025.39},
  annote =	{Keywords: plane tilings, polygons, undecidability, co-RE}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.4
The Equivalence Problem of E-Pattern Languages with Length Constraints Is Undecidable

Authors: Dirk Nowotka and Max Wiedenhöft

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only terminals. Length constraints restrict valid substitutions of variables by associating the variables of a pattern with a system (or disjunction of systems) of linear diophantine inequalities. Pattern languages with length constraints contain only words in which all variables are substituted to words with lengths that fulfill such a given set of length constraints. We consider membership, inclusion, and equivalence problems for erasing and non-erasing pattern languages with length constraints. Our main result shows that the erasing equivalence problem - one of the most prominent open problems in the realm of patterns - becomes undecidable if length constraints are allowed in addition to variable equality. Additionally, it is shown that the terminal-free inclusion problem, a prominent problem which has been shown to be undecidable in the binary case for patterns without any constraints, is also generally undecidable for all larger alphabets in this setting. Finally, we also show that considering regular constraints, i.e., associating variables also with regular languages as additional restrictions together with length constraints for valid substitutions, results in undecidability of the non-erasing equivalence problem. This sets a first upper bound on constraints to obtain undecidability in this case, as this problem is trivially decidable in the case of no constraints and as it has unknown decidability if only regular or only length constraints are considered.
Cite as

Dirk Nowotka and Max Wiedenhöft. The Equivalence Problem of E-Pattern Languages with Length Constraints Is Undecidable. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nowotka_et_al:LIPIcs.CPM.2025.4,
  author =	{Nowotka, Dirk and Wiedenh\"{o}ft, Max},
  title =	{{The Equivalence Problem of E-Pattern Languages with Length Constraints Is Undecidable}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.4},
  URN =		{urn:nbn:de:0030-drops-230988},
  doi =		{10.4230/LIPIcs.CPM.2025.4},
  annote =	{Keywords: Patterns, Pattern Languages, Length Constraints, Regular Constraints, Decidability, Undecidability, Membership, Inclusion, Equivalence}
}
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}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2025.24
Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly

Authors: Tim Gomez, Elise Grizzell, Asher Haun, Ryan Knobel, Tom Peters, Robert Schweller, and Tim Wylie

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

Abstract
The Tile Automata (TA) model describes self-assembly systems in which monomers can build structures and transition with an adjacent monomer to change their states. This paper shows that seeded TA is a non-committal intrinsically universal model of self-assembly. We present a single universal Tile Automata system containing approximately 4600 states that can simulate (a) the output assemblies created by any other Tile Automata system Γ, (b) the dynamics involved in building Γ’s assemblies, and (c) Γ’s internal state transitions. It does so in a non-committal way: it preserves the full non-deterministic dynamics of a tile’s potential attachment or transition by selecting its state in a single step, considering all possible outcomes until the moment of selection. The system uses supertiles, each encoding the complete system being simulated. The universal system builds supertiles from its seed, each representing a single tile in Γ, transferring the information to simulate Γ to each new tile. Supertiles may also asynchronously transition states according to the rules of Γ. This result also implies IU for pairwise asynchronous Cellular Automata.
Cite as

Tim Gomez, Elise Grizzell, Asher Haun, Ryan Knobel, Tom Peters, Robert Schweller, and Tim Wylie. Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 24:1-24:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gomez_et_al:LIPIcs.SAND.2025.24,
  author =	{Gomez, Tim and Grizzell, Elise and Haun, Asher and Knobel, Ryan and Peters, Tom and Schweller, Robert and Wylie, Tim},
  title =	{{Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{24:1--24:6},
  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.24},
  URN =		{urn:nbn:de:0030-drops-230772},
  doi =		{10.4230/LIPIcs.SAND.2025.24},
  annote =	{Keywords: Intrinsic Universality, Tile Automata, Cellular Automata, Self-assembly}
}
  • Refine by Type
  • 24 Document/PDF
  • 17 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 15 2025
  • 1 2024
  • 2 2023
  • 3 2021
  • Show More...

  • Refine by Author
  • 9 Woods, Damien
  • 4 Patitz, Matthew J.
  • 4 Schweller, Robert
  • 4 Shalaby, Ahmed
  • 3 Demaine, Erik D.
  • Show More...

  • Refine by Series/Journal
  • 22 LIPIcs
  • 1 OASIcs
  • 1 DagRep

  • Refine by Classification
  • 12 Theory of computation → Models of computation
  • 4 Theory of computation → Computational geometry
  • 4 Theory of computation → Problems, reductions and completeness
  • 2 Applied computing → Chemistry
  • 2 Computer systems organization → Molecular computing
  • Show More...

  • Refine by Keyword
  • 6 self-assembly
  • 3 Self-assembly
  • 3 minimum free energy
  • 3 model of computation
  • 2 DNA
  • 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