BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:2423@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20180628T140000
DTEND;TZID=Europe/Paris:20180628T160000
DTSTAMP:20241209T220034Z
URL:https://www.i2m.univ-amu.fr/evenements/complexite-algorithmique-des-in
 variants-de-type-croissance-des-sous-decalages-de-type-fini-sous-contraint
 e-dynamique/
SUMMARY:Silvère Gangloff (I2M\, Aix-Marseille Université): Complexité al
 gorithmique des invariants de type croissance des sous-décalages de type 
 fini sous contrainte dynamique
DESCRIPTION:Silvère Gangloff: Complexité algorithmique des invariants de 
 type croissance des sous-décalages de type fini sous contrainte dynamique
 \nLes sous-décalages multidimensionnels (SFT) sont des ensembles de color
 ations d'une grille régulière innie (Zd\,d ≥ 2) dénis par lois locale
 s. Ces objets sont impliqués dans plusieurs domaines des mathématiques e
 t en particulier la physique statistique. Un problème important dans ce c
 adre est de trouver une formule pour l'entropie. Excepté pour quelques mo
 dèles\, une telle formule n'est pas connue. De plus\, il a été démontr
 é relativement récemment qu'il n'existe pas de méthode pour calculer (a
 lgorithmiquement) l'entropie de ces systèmes. Par conséquent\, une appro
 che naturelle au problème est de chercher une sous-classe (maximale) sur 
 laquelle il existe un algorithme permettant de calculer uniformément l'en
 tropie.\n\nDans ce texte\, on propose des résultats reliés à ce problè
 me. Les plus important d'entre eux sont: (1) L'existence de SFT apériodiq
 ues vériant une variante de la propriété d'assemblage introduite ici et
  appelée assemblage linéaire\; (2) Une caractérisation des valeurs de l
 'entropie pour ces SFT (répondant en particulier à une question ouverte 
 de Hochman et Meyerovitch)\; (3) Une caractérisation d'un seuil pour la c
 alculabilité de l'entropie pour les sous-décalages multidimensionnels à
  language décidable\; (4) Une caractérisation des valeurs possibles de l
 a dimension entropique pour les SFT tridimensionnels minimaux.\nLes deux r
 ésultats de caractérisation peuvent être interprétés comme une approx
 imation par le haut de classes de SFT optimales sur lesquelles l'entropie 
 (resp. la dimension entropique) peut être calculé uniformément\, étend
 ant le domaine dynamique sur lequel un calcul universel peut être implém
 enté dans les SFT. Le résultat sur le seuil caractérise une classe opti
 male mais pour les sous-décalage à language décidable\, classe un peu p
 lus souple que celle des SFT. Un problème important reste ouvert: celui d
 e trouver une classe optimale pour les SFT multidimensionnels. De plus\, o
 n étend le problème à l'intervalle unité\, et caractérise les valeurs
  possibles de l'entropie pour les fonctions calculables de l'intervalle.\n
 \nMots clés : sous-décalages\, entropie\, invariants topologiques\, calc
 ulabilité.\n\nAlgorithmic complexity of growth-type invariants of SFT und
 er dynamical constraints\nMultidimensional subshifts of nite type (SFT) ar
 e sets of colorings of an innite regular grid (Zd\,d ≥ 2) dened by local
  rules. These objects are involved in many areas of mathematics and in par
 ticular statistical physics. One important problem in this setting is to c
 ompute the entropy with a formula. Unfortunately\, it was proved\, quite r
 ecently\, that there can not be a general method to compute (algorithmical
 ly) the entropy of these systems. The subsequent approach to the problem i
 s to seek for a subclass on which the entropy can be computed algorithmica
 lly. That is the main motivation to study the algorithmical complexity of 
 SFT in subclasses dened by dynamical constraints.\nIn this text\, we expos
 e results related to this problem. The most saliant ones are: (1) The exis
 tence of aperiodic subshifts of finite type under linear version block glu
 ing constraint\, introduced here\; (2) a characterization of the values of
  the entropy for these subshifts (this answers an open question by Hochman
  and Meyerovitch)\; (3) a characterization of a threshold on a quantified 
 version of the irreducibility property for the computability of the entrop
 y of decidable subshifts\; (4) a characterization of the entropy dimension
 s of minimal tridimensional SFT. The two characterization results can be i
 nterpreted as the approximation from above of some classes of SFT in which
  the possibility to embed universal computation (and thus have the non-com
 putability of the entropy) vanishes. The result on the threshold character
 ize an optimal class but is related to decidable subshifts. A challenging 
 open question is to find a similar result for multidimensional SFT. Moreov
 er\, we extend this investigation on the unit interval and characterize th
 e values of the entropy of computable interval maps.\nDirecteurs de thèse
 \nMathieu Sablik et Guillaume Theyssier\n\nLien: theses.fr
CATEGORIES:Soutenance de thèse,GDAC
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20180325T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR