Une méthode de programmation parallèle : d’une formule logique à un programme d’automate cellulaire

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



Retour en haut