A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
For researchers in DNA self-assembly and tile assembly models, this establishes a fundamental lower bound and clarifies the role of non-determinism in non-cooperative systems.
The paper proves that non-determinism is strictly necessary for assembling efficient paths in directed non-cooperative tile assembly systems, and shows that constructing a square of width n requires at least 2n-1 tile types, which is asymptotically optimal.
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 where assemblies do not need to cover the whole plane and some mismatches may occur). Introduced by P.E. Meunier, 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. Later, efficient paths were improved to be able to reach a distance of n log(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, a model called directed non-cooperative aTAM. This variant of aTAM is the only one who was shown to be decidable. In this paper, we prove that this non-determinism is strictly necessary for assembling the efficient paths. 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.