Laboratoire
Équipes
Membres
Événements
Info scientifique
Info. pratiques
Intranet LIGM
Retour à l'accueil
Séminaire Algo - Pascal Vanier
Séminaire Algo - Pascal Vanier Age: 330 days ![]() Pascal Vanier Points apériodiques dans les espaces de pavage bidimensionnels Salle de séminaire (4B125) - Bâtiment Copernic Abstract: La théorie des espaces de pavages a été profondément façonnée par le résultat historique de Berger : un jeu de tuiles fini peut ne paver le plan que de manière apériodique. Ces points apériodiques sont au c r de nombreuses directions de recherche du domaine, en mathématiques comme en informatique. Dans cette exposé, nous répondons aux questions suivantes en dimension 2 : 1. Quelle est la complexité calculatoire de déterminer si un jeu de tuiles (espace de type fini) possède un point apériodique ? 2. Comment se comportent les espaces de pavages ne possédant aucun point apériodique ? Nous montrons qu'un espace de pavage 2D sans point apériodique a une structures très forte : il est "équivalent" (presque conjugué) à un espace de pavage 1D, et ce résultat s'applique aux espaces de type fini ou non. Nous en déduisons que le problème de posséder un point apériodique est co-récursivement-énumérable-complet, et que la plupart des propriétés et méthodes propres au cas 1D s'appliquent aux espaces 2D sans point apériodiques. La situation en dimension supérieure semble beaucoup moins claire. Cet exposé est issu d'une collaboration avec Anael Grandjean et Benjamin Hellouin de Menibus. |