Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.18630 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913099125096448 |
|---|---|
| author | Ivanov, Sergiu Regnault, Damien |
| author_facet | Ivanov, Sergiu Regnault, Damien |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18630 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system Ivanov, Sergiu Regnault, Damien Computational Complexity 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. |
| title | A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2405.18630 |