Les automates de Büchi sont l’extension naturelle des automates finis à un modèle de calcul qui accepte des entrées de longueur infinie. On dit qu’un sous-ensemble X des réels est r-automatique s’il existe un automate de Büchi qui accepte (l’une des) représentations en base-r de chaque élément de X et rejette les représentations en base-r de chaque élément dans son complément. On peut définir de manière analogue des sous-ensembles r-automatique d’arités supérieures, et ces ensembles présentent souvent un comportement de type fractal – par exemple, l’ensemble de Cantor est 3-automatique. Il existe des liens intéressants entre la géométrie fractale et les automates de Büchi, et on les considère du point de vue de la théorie des modèles. Dans cet exposé, on présente une caractérisation des cas dans lesquels les différentes notions de dimension fractale concordent et des cas dans lesquels elles ne concordent pas pour les ensembles r-automatique.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne