Actions automatiques

par Laurent Bartholdi

lundi 7 oct. 2024, 16:00 → 17:00 Europe/Paris

 

J'introduirai une notion générale d'action automatique, basée sur les automates de Büchi, et montrerai comment elle unifie un grand nombre de sous-classes, en particulier les groupes automatiques à la Cannon, Thurston et al ; les groupes de transducteurs d'Aleshin, Grigorchuk, Sushchansky, Sidki et al ; les sous-décalages substitutifs ; et les systèmes dynamiques holomorphes.

Je présenterai quelques algorithmes pour ces groupes, et en particulier je montrerai sous une condition supplémentaire (les actions bornées) que leur relation d'orbite est calculable et régulière. Cela conduit à des résultats de décidabilité, comme le fait que le problème de l'ordre (un élément est-il d'ordre fini ou infini?), de l'apériodicité, de la minimalité, etc. pour les transformations automatiques est décidable.

Je détaillerai les applications à la dynamique symbolique : en particulier, il est décidable si un sous-décalage substitutif est apériodique, minimal, topologiquement transitif, etc. ; et à la dynamique complexe : il est décidable, par exemple, si un ensemble de Julia est un tapis de Sierpinski.