Search Results

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.