Formation de pavages par auto-assemblage et auto-stabilisation

This habilitation à diriger des recherches deals with tilings, a computational model where tiles are bound together in order to do computation as complex as the ones done by Turing Machines. Nevertheless, tilings have a major flaw as a computational model: the tiles should be carefully assembled in order to produce the desired result. Since tilings are used for studying nanoscopic structures such as crystals or for modeling interactions of DNA strands, errors appearing during the assembly should be taken in consideration. We are focusing here on two ways to deal with this problem: self-assembly where all possibilities are taken into account during the assembly and self-stabilization where tiles can locally move in order to correct faults done during the assembly.Cette habilitation à diriger des recherches est consacrée aux pavages, un modèle de calcul utilisant des tuiles pour former des assemblages capables de faire des calculs d’une complexité équivalente à ceux d’une machine de Turing. En tant que modèle de calcul, les pavages présentent néanmoins un défaut majeur: les tuiles doivent être placées minutieuse- ment pour obtenir l’assemblage souhaité. Les pavages étant utilisés pour étudier des structures nanoscopiques en cristallographie ou pour modéliser l’interaction de brins d’ADN, il est nécessaire d’envisager que l’assemblage du pavage ne se déroule pas parfaitement. Nous nous intéressons ici à deux approches pour gérer ce problème: l’auto-assemblage où les différentes possibilités de placement des tuiles lors de l’assemblage sont prises en compte et l’auto-stabilisation ou` les tuiles peuvent se réorganiser localement pour corriger d’éventuelles erreurs survenues lors de leur placement