November 4, 2019
Tien Thao N’guyen (LACL)Un grand nombre d’automates cellulaires ont été donnés sous forme de table de transition construite à la main. La méthodologie des “champs cellulaires” donne les principes de conception modulaire et de génération de la table de transition en dernière étape, comme c’est le cas pour le code source d’un langage de programmation de haut niveau et leur fichier exécutable binaire. Nous vérifions si les tables ainsi générées peuvent être optimisées pour être aussi petites que leurs contreparties construites à la main. Ceci est fait dans le cas particulier d’un automate cellulaire qui résout le problème de synchronisation des fusiliers (Firing Squad Synchronization problem en anglais) en utilisant des champs cellulaires. Nous étudions la structure interne de cette solution et ainsi que des notions de réduction dans la même veine que la minimisation des automates finis déterministe. La comparaison est faite avec la solution “à la main” de Noguchi.