Des conditions suffisantes pour qu’un shift 2D soit sofic
Julien Destombes
LIRMM, Univ. Montpellier
https://www.theses.fr/s174751
Date(s) : 16/11/2021 iCal
11h00 - 12h00
Nous nous intéressons dans cette présentation à des conditions suffisantes pour qu’un shift multidimensionnel soit sofic. Nous verrons ainsi que si la complexité par bloc d’un shift est très petite, i.e. sous-linéaire, alors le shift est sofic.
La preuve de ce résultat utilise différents outils : elle est basée sur un jeu de tuiles dont les pavages sont auto-similaires, tiré de l’article “The expressiveness of quasiperiodic and minimal shifts of finite type” de A. Romashchenko et B. Durand. Elle utilise un modèle de calcul, les automates cellulaires non-déterministes à une dimension, pour effectuer des calculs de manière efficace ; enfin, elle utilise un résultat sur les flots pouvant circuler dans des graphes d’un certain type.
Emplacement
I2M Luminy - Ancienne BU, Salle Séminaire2 (RdC)
Catégories
