Problèmes de décision sur les pavages géométriques : Patates de Wang et complexité locale finie
Victor Lutfalla
I2M
https://lutfalla.fr/
Date(s) : 19/11/2024 iCal
11h00 - 12h00
La complexité locale finie est la propriété d’un sous-shift de pavages géométriques qui permet d’énumérer les motifs locaux et donc de considérer les problèmes de décision classiques tels que le problème du Domino.
Dans cet exposé nous présenterons le fait que le problème de déterminer si un sous-shift de pavages géométriques est à complexité locale finie est indécidable.
Nous adaptons la construction de Gurevich et Kuryakov pour réduire ce problème au problème de l’arrêt des machines de Turing.
Emplacement
I2M Luminy - TPR2, Salle de Séminaire 304-306 (3ème étage)
Catégories
