[CoA 2014] Florent Becker

troisièmes journées du GT CoA Complexité et Algorithmes :
Algorithmes naturels
du mercredi 10 septembre 12h30 au vendredi 12 septembre 13h30, Université Paris Diderot
LIAFA, Salle 1009, Bâtiment Sophie Germain Paris 13ème

16:00-17:00 - Exposé invité n°2 : Florent BECKER (LIFO)
You Look Funny when you Simulate: The Price of Intrinsic Universality in Self-Assembly

Self-assembly is a tile-based model of natural computation, which is notably not totally unlike what can be implemented using DNA. It has been known to be Turing Complete for a long time, but recent works by Patitz, Meunier, Woods and others have brought forward and studied the notions of internal simulation of self-assembly (simulating self-assembly systems by other self-assembly systems) and intrinsic universality. Yet, simulator constructions tend to exhibit peculiar behaviours such as using mismatches between tiles in order to implement locking of critical sections. Is this complexity necessary?
In this talk, I will present some classes of behavior for self-assembly systems, and show that they are actually separated, and which of them have a complete system. In doing so, we will explore the tools for a detailed look into the dynamics of self-assembly systems: Turing complexity, but also the less familiar bisimilarity lemma and cutspaces.