Self-assemblying (classes of) shapes with a constant number of tiles.
Résumé
Squares are the most studied shapes in the tile assembly model. Adleman et al. proved that the program size complexity of an $n \times n$ square is $\Theta(\frac{\log n}{\log\log n})$. In other words, for each $n$ we need a different set of tiles. Also, the size of the set increases with $n$. Our approach is to fix {\it a priori} the set of tiles in such a way that it always self-assembles into an $N \times N$ square. If $n$ is an arbitrary positive integer, we show how to calculate the tile concentrations in order to ensure that $\E(N)=n$. To our knowlwdge, the tile concentrations, a parameter of the original model, has never been seriously considered before. We claim that it is therefore not necessary to construct the tiles (which are in fact tiny molecules) for each shape we are asked to assemble. These tiny molecules are, for us, fixed primitives. In order to obtain (in expectation) the required shape, we only need to ``play'' with the concentrations. This is, of course, a standard procedure in Chemistry and Biology. Let $d$ be a distance in ${\Z}^2$. In the present work we tackle the specific problem of constructing tile systems that assemble into shapes of the form $\{ x \in {\Z}^2 \> \vert \> d(x,0) \leq N\}$ and such that $\E(N)=n$. We solve the problem for the max distance $d_{\infty}$ and for the $d_1$ distance. In the first case the induced shapes are squares while in the second case the induced shapes are diamonds. Diamonds are much more difficult to produce than squares. We leave as an open problem the Euclidean distance $d_2$, which induces the class of ``discrete circles''.
Les carrés sont les formes les plus étudiés dans le modèle d'auto-assembalge. Adleman et al ont prouvé que complexité en taille d'un carré n x n est $\Theta(\frac{\log n}{\log\log n})$. En d'autres termes, le nombre de tuiles nécessaires pour réaliser le carré n x n augmentées avec n.
Notre approche consiste à fixer a priori l'ensemble des tuiles de telle façon que les seuls auto-assemblages terminaux possibles soient les carrés. pour tout entier positif n, nous montrons comment choisir les concentrations de tuiles, qui sont un paramètre du modèle original, n'ont jamais été sérieusement considérées auparavant. Les tuiles représentent des petites molécules pouvant s'assembler. Ces molécules de bases sont, pour nous, des primitives fixées . Dans le but d'obtenir (en moyenne) la forme de la taille requise, nous avons seulement besoin , de "jouer" sur les concentrations. Ceci est, évidemment, une procédure standard en chimie et en biologie. Soit d une distance dans ${\Z}^2$. dans cet article, nous travaillons sur le problème spécifique de construire des systèmes de tuiles qui s’assemblent en formes du type $\{ x \in {\Z}^2 \> \vert \> d(x,0) \leq N\}$ and such that $\E(N)=n$. Nous résolvons le problème pour la distance $d_{\infty}$ et pour la distance $d_1$. Dans le premier cas, les formes induites sont des carrés tandis que dans le deuxième cas, ces sont des "carreaux". Les carreaux sont beaucoup plus difficiles à produire que les carrés. Nous laissons ouvert le problème pour la distance Euclidienne $d_2$, sui induit la classe des "cercles discrets".
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|