4 mars 2024
Léo Paviet Salomon (GREYC, Université Caen Normandie)Un résultat classique dans l’étude des langages formels est le théorème de Myhill-Nerode, qui donne des conditions nécessaires et suffisantes en terme de langages résiduels pour qu’un langage soit régulier. Dans cet exposé, on essaiera de montrer comment cet outil a été adapté à l’étude des espaces de pavages, où les configurations ne sont plus des mots finis mais des coloriages multidimensionnels infinis. En particulier, on étudiera l’/entropie d’extension/, introduite par R.Pavlov et T.French, qui représente le taux de croissance de cet équivalent aux langages résiduels. On donnera plusieurs caractérisations obtenus sur cette entropie grâce à la théorie de la calculabitlité, sur plusieurs clases de pavages mono- et multidimensionnels.