Résumé : I will present a general notion of automatic action, based on Büchi automata, and show how it unifies a large number of subclasses, in particular the automatic groups by Cannon, Thurston et al., the transducer groups by Aleshin, Grigorchuk, Sushchansky, Sidki et al., and substitutional subshifts. I will present some algorithms for these groups, and in particular show under an extra condition (boundedness) that their orbit relation is computable. This will have strong decidability consequences, such as that the order problem, aperiodicity, minimality, etc. for automatic transformations is decidable.

Keywords : substitutional subshifts; automatic structures