Vidéos de la preuve complète
diaporama

We prove here a result which strongly hints at the computational 
weakness of a model of tile assembly that has so far resisted many 
attempts of formal analysis or positive constructions. Specifically, we 
prove that, in Winfree's abstract Tile Assembly Model, when restricted 
to use only noncooperative bindings, any long enough path starting from 
the seed that can grow in all terminal assemblies is \emph{pumpable}, 
meaning that this path can be extended into an infinite, ultimately 
periodic path.

This result can be seen as a geometric generalization of the pumping 
lemma of finite state automata, and is a great step to solve the 
question of what can be computed deterministically in this model. 
Moreover, this question has motivated the development of a new method 
called \emph{visible glues}.

Tile assembly (including non-cooperative tile assembly) was originally 
introduced by Winfree and Rothemund to understand how to \emph{program 
shapes}. The non-cooperative variant, also known as temperature 1 tile 
assembly, is the model where tiles are allowed to bind as soon as they 
match on one side, whereas in cooperative tile assembly, some tiles need 
to match on several sides in order to bind. Previously, exactly one 
known result showed a restriction on the assemblies general 
non-cooperative self-assembly could achieve, without any implication on 
its computational expressiveness. With non-square tiles (like 
polyominos), other recent works have shown that the model quickly 
becomes computationally powerful.