Andrei Romashchenko (LIRMM, Univ. Montpellier)

C’est un sujet de dynamique symbolique. Nous fournissons des exemples de sous- shifts effectifs et non sofics sur Z 2 avec une complexité de bloc très faible: le nombre de motifs admissibles de taille N x N croît comme poly( N ). La preuve est rigolote, parce qu’on utilise une technique substantiellement algorithmique (complexité de Kolmogorov à temps borné) pour répondre une question mathématique, qui n’a rien à voir avec la complexité de calcul.

C’est un travail commun avec Julien Destombes, STACS 2019 https://arxiv.org/abs/1805.03929