Théo Grente
GREYC, Université de Caen Normandie
https://www.researchgate.net/profile/Theo-Grente
Date(s) : 27/04/2021 iCal
11 h 00 min - 12 h 00 min
Les automates cellulaires constituent le modèle de calcul parallèle et local par excellence. Ainsi, on peut trouver dans la littérature de nombreux algorithmes sur ce modèle de calcul. Ces algorithmes sont souvent décrits sous la forme de signaux et collisions, sans détailler le programme de l’automate cellulaire qui en résulte.
Je présenterai dans cette exposé une méthode permettant d’obtenir ce programme de manière automatique. Cette méthode consiste dans un premier temps à programmer en logique l’induction résolvant un problème (par exemple, un schéma de signaux et collisions), puis dans un second temps, à appliquer un processus automatique aboutissant au programme de l’automate cellulaire résolvant ce problème.
En plus de cette méthode, je présenterai aussi les caractérisations logiques de chacune des trois classes de complexité en temps minimal des automates cellulaires obtenues par celle-ci, en m’attardant sur la plus générale.
Enfin, si le temps me le permet, j’aborderai un résultat de reconnaissance des langages conjonctifs (une extension des langages algébriques) obtenu par notre méthode de programmation par la logique.
A parallel programming method: from a logical formula to a cellular automaton program
Cellular automata constitute the ultimate model of parallel and local computation. Thus, one can find in the literature many algorithms on this computational model. These algorithms are often described in the form of signals and collisions, without detailing the resulting cellular automaton program. I will present in this talk a method to obtain this program automatically. This method consists in a first step in programming in logic the induction solving a problem (for example, a diagram of signals and collisions), then in a second step, in applying an automatic process resulting in the program of the cellular automaton solving this problem.
In addition to this method, i will also present the logical characterizations of each of the three classes of complexity in minimal time of cellular automata obtained by this one, while dwelling on the most general one. Finally, if time permits, i will discuss a result of recognition of connective languages (an extension of algebraic languages) obtained by our method of programming by logic.
https://tel.archives-ouvertes.fr/tel-03093951
Lien zoom :
https://univ-amu-fr.zoom.us/j/98106380073?pwd=ZUtnMWdhZjJpdmc3czZmcS8xSkEydz09
Emplacement
Site Sud, Luminy, TPR2, Salle de Séminaire 304-306 (3ème étage)
Catégories