Strict Self-Assembly of Discrete Self-Similar Fractal Shapes
Auto-assemblage strict de formes fractales
Résumé
This paper gives a (polynomial time) algorithm to decide whether a given Discrete Self-Similar Fractal Shape can be assembled in the aTAM model.
In the positive case, the construction relies on a Self-Assembling System in the aTAM which strictly assembles a particular self-similar fractal shape, namely a variant $K^\infty$ of the Sierpinski Carpet. We prove that the aTAM we propose is correct through a novel device, \emph{self-describing circuits} which are generally useful for rigorous yet readable proofs of the behaviour of aTAMs.
We then discuss which self-similar fractals can or cannot be strictly self-assembled in the aTAM. It turns out that the ability of iterates of the generator to pass information is crucial: either this \emph{bandwidth} is eventually sufficient in both cardinal directions and $K^\infty$ appears within the fractal pattern after some finite number of iterations, or that bandwidth remains ever insufficient in one direction and any aTAM trying to self-assemble the shape will end up either bounded with an ultimately periodic pattern covering arbitrarily large squares. This is established thanks to a new characterization of the productions of systems whose productions have a uniformly bounded treewidth.
Cet article présente un algorithme en temps polynomial pour déterminer si une forme fractale discrète donnée peut être auto-assemblée dans le modèle aTAM.
Dans le cas positif, on obtient une construction explicite qui repose sur l'auto-assemblage d'une fractale particulière —$K^\infty$, une variante du tapis de Sierpiński. La correction de cet assemblage se fait au moyen d'un nouvel outil, les circuits auto-descriptif, qui permettent des preuves rigoureuses mais relativement lisibles du comportement des systèmes aTAM.
La distinction effectuée par l'algorithme entre les fractales qui peuvent être auto-assemblées et les autres repose sur la capacité de leurs itérées à faire circuler de l'information. Cette capacité se mesure à leur \emph{bande passante}. Si, à force d'itérer le générateur de la fractale $F$, la bande passante devient suffisante dans les deux directions cardinales, on peut alors plonger $K^\infty$ et son circuit auto-descriptif dans $F$ et ainsi l'assembler. Sinon, toute production infinie d'un système aTAM dont les productions sont cantonnées à $F$ contient des carrés périodiques arbitrairement grands. Aucune de ces productions ne peut donc avoir $F$ tout entier comme support. La périodicité de ces productions est établie grâce à une caractérisation nouvelle des productions de systèmes dont toutes les productions sont de largeur arborescente bornée.
Domaines
Mathématique discrète [cs.DM]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|---|
| licence |
