Séminiare Algorithmique « Sous-shifts au langage stable », Samuel Petite (LAMFA, Univ. Picardie)

Les sous-shifts au langage stable forment une classe de sous-shifts qui a été récemment introduite par V. Cyr et B. Kra. Cette famille contient de nombreux exemples classiques de sous-shifts, de diverses complexités allant des systèmes d’entropie strictement positive, comme les sous-shifts de type fini, aux systèmes de faible complexité, comme les sous-shifts de complexité linéaire. Ils sont génériques parmi la famille des sous-shifts. Nous présentons dans cet exposé quelques unes de leurs propriétés, notamment celles concernant les automates cellulaires les préservant.