More Like this

1. Brief Announcement: Intrinsic Universality in Seeded Active Tile Self-Assembly

   https://doi.org/10.4230/lipics.sand.2025.24  

   Gomez, Tim; Grizzell, Elise; Haun, Asher; Knobel, Ryan; Peters, Tom; Schweller, Robert; Wylie, Tim (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meeks, Kitty; Scheideler, Christian (Ed.)

   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. 

   more » « less
2. Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

   https://doi.org/https://doi.org/10.1007/s00453-019-00573-w  

   Schweller, R.; Winslow, A.; Wylie, T. (April 2019, Algorithmica)

   Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information. In particular, for all n∈N , we assemble n×n squares using O(2log∗n) tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with O(2log∗K) tiles, where K denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct n×O(1) rectangles using only O(logn/loglogn) tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature. These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion. 

   more » « less
3. Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract Tile Assembly Model

   Becker, Florent; Hader, Daniel; Patitz, Matthew J (January 2025, Society for Industrial and Applied Mathematics)

   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 a quine, a program which prints its own output, to the language of tile-assembly naturally induces a fractal structure. The other construction introduces self-describing circuits as 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 ℤ2 will generate an aTAM producible DSSF. To this end, we also introduce the Tree Pump Theorem, a result analogous to the important Window Movie Lemma, but with requirements on the set of productions rather than on the self-assembling system itself. 

   more » « less
4. Mapping of 30-meter resolution tile-drained croplands using a geospatial modeling approach

   https://doi.org/10.1038/s41597-020-00596-x  

   Valayamkunnath, Prasanth; Barlage, Michael; Chen, Fei; Gochis, David J.; Franz, Kristie J. (August 2020, Scientific Data)

   Abstract Tile drainage is one of the dominant agricultural management practices in the United States and has greatly expanded since the late 1990s. It has proven effects on land surface water balance and quantity and quality of streamflow at the local scale. The effect of tile drainage on crop production, hydrology, and the environment on a regional scale is elusive due to lack of high-resolution, spatially-explicit tile drainage area information for the Contiguous United States (CONUS). We developed a 30-m resolution tile drainage map of the most-likely tile-drained area of the CONUS (AgTile-US) from county-level tile drainage census using a geospatial model that uses soil drainage information and topographic slope as inputs. Validation of AgTile-US with 16000 ground truth points indicated 86.03% accuracy at the CONUS-scale. Over the heavily tile-drained midwestern regions of the U.S., the accuracy ranges from 82.7% to 93.6%. These data can be used to study and model the hydrologic and water quality responses of tile drainage and to enhance streamflow forecasting in tile drainage dominant regions. 

   more » « less
5. 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