More Like this

1. Strict Self-Assembly of Discrete Self-Similar Fractals in the Abstract Tile Assembly Model

   https://doi.org/10.1007/s00453-025-01340-w  

   Becker, Florent; Hader, Daniel; Patitz, Matthew (January 2026, Algorithmica)

   Abstract This paper answers a long-standing open question in tile-assembly theory, namely that it is possible to strictly assemble discrete self-similar fractals (DSSFs) in the abstract Tile-Assembly Model (aTAM). We prove this in 2 separate ways, each taking advantage of a novel set of tools. One of our constructions shows that specializing the notion of aquine, a program which prints its own output, to the language of tile-assembly naturally induces a fractal structure. The other construction introducesself-describing circuitsas a means to abstractly represent the information flow through a tile-assembly construction and shows that such circuits may be constructed for a relative of the Sierpinski carpet, and indeed many other DSSFs, through a process of fixed-point iteration. This later result, or more specifically the machinery used in its construction, further enable us to provide a polynomial time procedure for deciding whether any given subset of$$\mathbb {Z}^2$$will generate an aTAM producible DSSF. To this end, we also introduce theTree Pump Theorem, a result analogous to the importantWindow Movie Lemma, but with requirements on the set of productions rather than on the self-assembling system itself. This paper is an extension of a version that appeared in the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’25). 

   more » « less
2. Synchronous Versus Asynchronous Tile-Based Self-Assembly

   https://doi.org/10.4230/lipics.dna.31.9  

   Becker, Florent; Drake, Phillip; Patitz, Matthew J; Rogers, Trent A (August 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Schaeffer, Josie; Zhang, Fei (Ed.)

   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. 

   more » « less
3. Self-assembly of shapes at constant scale using repulsive forces

   https://doi.org/https://doi.org/10.1007/s11047-018-9707-9  

   Luchsinger, Austin; Schweller, Robert; Wylie, Tim (March 2019, Natural computing)

   The algorithmic self-assembly of shapes has been considered in several models of self-assembly. For the problem of shape construction, we consider an extended version of the two-handed tile assembly model, which contains positive (attractive) and negative (repulsive) interactions. As a result, portions of an assembly can become unstable and detach. In this model, we utilize fuel-efficient computation to perform Turing machine simulations for the construction of the shape. In this paper, we show how an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (based on the shape’s Kolmogorov complexity). We achieve this at O(1) scale factor in this straightforward model, whereas all previous results with sublinear scale factors utilize powerful self-assembly models containing features such as staging, tile deletion, chemical reaction networks, and tile activation/deactivation. Furthermore, the computation and construction in our result only creates constant-size garbage assemblies as a byproduct of assembling the shape. 

   more » « less
4. Simulation of the Abstract Tile Assembly Model Using Crisscross Slats

   https://doi.org/10.4230/LIPIcs.DNA.30.3  

   Drake, Phillip; Hader, Daniel; Patitz, Matthew J (September 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Seki, Shinnosuke; Stewart, Jaimie Marie (Ed.)

   The abstract Tile Assembly Model (aTAM) provides an excellent foundation for the mathematical study of DNA-tile-based self-assembling systems, especially those wherein logic is embedded within the designs of the tiles so that they follow prescribed algorithms. While such algorithmic self-assembling systems are theoretically powerful, being computationally universal and capable of building complex shapes using information-theoretically optimal numbers of tiles, physical DNA-based implementations of these systems still encounter formidable error rates and undesired nucleation that hinder this theoretical potential. Slat-based self-assembly is a recent development wherein DNA forms long slats that combine together in 2 layers, rather than square tiles in a plane. In this approach, the length of the slats is key; while tiles typically only bind to 2 neighboring tiles at a time, slats may bind to dozens of other slats. This increased coordination between slats means that several mismatched slats must coincidentally meet in just the right way for errors to persist, unlike tiles where only a few are required. Consequently, while still a novel technology, large slat-based DNA constructions have been successfully implemented in the lab with resilience to many tile-based construction problems. These improved error characteristics come at a cost however, as slat-based systems are often more difficult to design and simulate than tile-based ones. Moreover, it has not been clear whether slats, with their larger sizes and different geometries, have the same theoretical capabilities as tiles. In this paper, we show that slats are capable of doing anything that tiles can, at least at scale. We demonstrate that any aTAM system may be converted to and simulated by an effectively equivalent system of slats. Furthermore, we show that these simulating slat systems can be made more efficiently, using shorter slats and a smaller scale factor, if the simulated tile system avoids certain uncommon growth patterns. Specifically, we consider 5 classes of aTAM systems with increasing complexity, from zig-zag systems which grow in a rigid pattern to the full class of all aTAM systems, and show how they may be converted to equivalent slat systems. We show that the simplest class may be simulated by slats at only a 2c × 2c scale, where c is the freely chosen coordination number of the slats, and further show that the full class of aTAM systems can be simulated at only a 5c × 5c scale. These results prove that slats have the full theoretical power of aTAM tiles while also providing constructions that are compact enough for potential DNA-based implementations of slat systems that are both capable of powerful algorithmic self-assembly and possessing of the strong error resilience of slats. 

   more » « less
5. Simulation of the abstract Tile Assembly Model using crisscross slats (extended version)

   https://doi.org/10.1007/s11047-025-10057-2  

   Drake, Phillip; Hader, Daniel; Patitz, Matthew J (January 2026, Natural Computing)

   Abstract The abstract Tile Assembly Model (aTAM) provides an excellent foundation for the mathematical study of DNA-tile-based self-assembling systems, especially those wherein logic is embedded within the designs of the tiles so that they follow prescribed algorithms. While such algorithmic self-assembling systems are theoretically powerful, being computationally universal and capable of building complex shapes using information-theoretically optimal numbers of tiles, physical DNA-based implementations of these systems still encounter formidable error rates and undesired nucleation that hinder this theoretical potential. Slat-based self-assembly is a recent development wherein DNA forms long slats that combine together in 2 layers, rather than square tiles in a plane. In this approach, the length of the slats is key; while tiles typically only bind to 2 neighboring tiles at a time, slats may bind to dozens of other slats. This increased coordination between slats means that several mismatched slats must coincidentally meet in just the right way for errors to persist, unlike tiles where only a few are required. Consequently, while still a novel technology, large slat-based DNA constructions have been successfully implemented in the lab with resilience to many tile-based construction problems. These improved error characteristics come at a cost however, as slat-based systems are often more difficult to design and simulate than tile-based ones. Moreover, it has not been clear whether slats, with their larger sizes and different geometries, have the same theoretical capabilities as tiles. In this paper, we show that slats are capable of doing anything that tiles can, at least at scale. We demonstrate that any aTAM system may be converted to and simulated by an effectively equivalent system of slats. Furthermore, we show that these simulating slat systems can be made more efficiently, using shorter slats and a smaller scale factor, if the simulated tile system avoids certain uncommon growth patterns. Specifically, we consider 5 classes of aTAM systems with increasing complexity, from zig-zag systems which grow in a rigid pattern to the full class of all aTAM systems, and show how they may be converted to equivalent slat systems. We show that the simplest class may be simulated by slats at only a$$2c \times 2c$$scale, wherecis the freely chosen coordination number of the slats, and further show that the full class of aTAM systems can be simulated at only a$$5c \times 5c$$scale. These results prove that slats have the full theoretical power of aTAM tiles while also providing constructions that are compact enough for potential DNA-based implementations of slat systems that are both capable of powerful algorithmic self-assembly and possessing of the strong error resilience of slats. This paper is an extended version of a version that appeared in the proceedings of the 30th International Conference on DNA Computing and Molecular Programming (DNA 30). 

   more » « less