Introduced in [Erik Winfree, 1998], the abstract tile assembly model (aTAM) is a model of DNA self-assembly. Most of the studies focus on cooperative aTAM where a form of synchronization between the tiles is possible. Simulating Turing machines is achievable in this context. Few results and constructions are known for the non-cooperative case (a variant of Wang tilings [Hao Wang, 1961] where assemblies do not need to cover the whole plane and some mismatches may occur). For example, assembly of a square of width n is done with 2n-1 tiles types whereas only Θ(log(n)/(log log(n))) are required for the cooperative case [Leonard M. Adleman et al., 2001]. Introduced by P.-É. Meunier in [Meunier, 2015], efficient paths are a non-trivial construction for non-cooperative aTAM designed with n different tile types and reaching a distance linearly greater than n. Improved in [Pierre-Étienne Meunier and Damien Regnault, 2019], efficient paths were shown to be able to reach a distance of nlog(n). Assembling them relies heavily on a form of "non-determinism". Indeed, the set of tiles may produce different finite terminal assemblies but they all contain the same efficient path. In this paper, we prove that this non-determinism is strictly necessary for assembling the efficient paths of [Pierre-Étienne Meunier and Damien Regnault, 2019]. More formally, we show that if the terminal assembly of a directed non-cooperative tile assembly system (a model where only one terminal assembly is produced) is finite then its width and length are linear in the number of tiles. This result also implies that the construction of a square of width n using 2n-1 tiles types is asymptotically optimal. Moreover, we hope that the techniques introduced here will lead to a better comprehension of the non-directed case.

We study the complexity relationship between three models of unbounded memory automata: nu-automata (ν-A), Layered Memory Automata (LaMA)and History-Register Automata (HRA). These are all extensions of finite state automata with unbounded memory over infinite alphabets. We prove that the membership problem is NP-complete for all of them, while they fall into different classes for what concerns non-emptiness. The problem of non-emptiness is known to be Ackermann-complete for HRA, we prove that it is PSPACE-complete for ν-A.

International audience

We prove a Pumping Lemma for the noncooperative abstract Tile Assembly Model, a model central to the theory of algorithmic self-assembly since the beginning of the field. This theory suggests, and our result proves, that small differences in the nature of adhesive bindings between abstract square molecules gives rise to vastly different expressive capabilities. In the cooperative abstract Tile Assembly Model, square tiles attach to each other using multi-sided cooperation of one, two or more sides. This precise control of tile binding is directly exploited for algorithmic tasks including growth of specified shapes using very few tile types, as well as simulation of Turing machines and even self-simulation of self-assembly systems. But are cooperative bindings required for these computational tasks? The definitionally simpler noncooperative (or Temperature 1) model has poor control over local binding events: tiles stick if they bind on at least one side. This has led to the conjecture that it is impossible for it to exhibit precisely controlled growth of computationally-defined shapes. Here, we prove such an impossibility result. We show that any planar noncooperative system that attempts to grow large algorithmically-controlled tile-efficient assemblies must also grow infinite non-algorithmic (pumped) structures with a simple closed-form description, or else suffer blocking of intended algorithmic structures. Our result holds for both directed and nondirected systems, and gives an explicit upper bound of (8|T|)4|T|+1(5|σ| + 6), where |T| is the size of the tileset and |σ| is the size of the seed assembly, beyond which any path of tiles is pumpable or blockable.