Michel BAUDERON
Michel Bauderon Professeur (Université Bordeaux 1)

Équipe LaBRI : Méthodes formelles
Courrier électronique : michel.bauderonarobaselabri.fr
Bureau : 107
Tél : +33 (0)5 40 00 24 95


Recherche

Grammaires de Pullback :
Un développement complet de la notion de grammaire de graphes par pullback fait l'objet de la thèse de Chen Rui, co-encadrée avec Olivier Ly et dont la soutenance a eu lieu le 21 Décembre 2007 (2 articles en préparation). Le résultat le plus important que nous ayons obtenu dans ce contexte est sans doute le fait que la réécriture de graphes par produit fibré est intrinsèquement context-free (ICGT'08) en utilisant la définition axiomatique donnée par Courcelle (1987). Pour illustrer la puissance du mécanisme, nous avons fourni dans ICGT'08 une grammaire de graphes context-free engendrant les grilles carrées et elles seules, contre-exemple classique à la " context-freeness " pour les grammaires d'hyperarcs. La puissance exacte de ce type de réécriture de graphes reste ouverte.
Ce résultat m'a conduit à développer un formalisme très général de réécriture dans une catégorie quelconque, soit par pushout, soit par pullback (travaux en collaboration avec O. Ly et R. Chen). Nous avons alors montré que de tels systèmes de réécritures étaient toujours context-free (CAI 2009). Dans le cas des mots, décrits comme des ordres totaux étiquetés par les lettres d'un alphabet, nous avons ainsi montré que la réécriture par pushout permet de décrire les classiques grammaires context-free au sens de Chomsky.
Les réécritures par pullback sont, elles, beaucoup plus puissantes, et nous avons montré (CAI 2009) qu'elles fournissent une grammaire context-free engendrant le langage anbncn, classique contre-exemple pour les mots.
Plus récemment, nous avons montré que la réécriture par pullback permet de décrire les grammaires à in-connues éparpillées (scattered non-terminal grammars), connues pour engendrer les grammaires récursive-ment énumérables, montrant ainsi que les grammaires récursivement énumérables sont context-free et remettant en cause la définition par l'exemple de la notion de grammaire context-free à la Chomsky (soumis).

Visualisation de graphes et exécution d'algorithmes distribués sur les graphes
Durant ma délégation CNRS au LIAMA (Beijing), j'ai participé au projet Netquest (INRIA), dirigé par Stéphane Grumbach. Il propose lui aussi une approche déclarative à l'écriture de programmes distribués en proposant Netlog, un langage de type Datalog complété par quelques opérateurs décrivant la communication au sein d'un réseau d'entités communicantes.
Je me suis surtout intéressé à la mise en œuvre concrète de Netlog en écrivant un compilateur pour une machine virtuelle s'appuyant sur un SGBD et en développant un environnement de développement, de simulation et de déboggage de programmes Netlog. Cet environnement permet de construire un graphe représentant un réseau de nœuds exécutant tous en temps réel le même programme Netlog, de visualiser cette exécution, de suivre les messages échangés, et d'effectuer une exécution pas à pas de ce programme. Le graphe est dynamique, puisque des nœuds mobiles peuvent dynamiquement créer des liens avec leurs voisins du moment.
Développé en C# sous .Net, cet environnement permet aussi d'intégrer via une connexion Bluetooth des smartphones exécutant un SGBD (par exemple SQLCE sous Windows Mobile 6.1).
Ce prototype une fois construit, j'ai piloté le portage de l'environnement sous Java.

Extrait de publications


Michel Bauderon, Christophe Bobineau, Stéphane Grumbach, Antoine Henry, Xin Qi, et al.. Netquest: An Abstract Model for Pervasive Applications. Seventh IEEE International Conference on Pervasive Computing (Pervasive 2009), 2009, Nara, Japan. LNCS, pp.467-481, 2009.

Olivier Ly, Michel Bauderon, Rui Chen. Context-free categorical grammars. 3rd International Conference on Algebraic Informatics, 2009, Thessaloniki, Greece. To appear, 2009.

Olivier Ly, Rui Chen, Michel Bauderon. Pullback Grammars are Context-Free. 4th International Conference on Graph Transformation (ICGT'08), 2008, Leicaster, United Kingdom. To be published, 2008.


Administration

2004-2008 : Attaché pour la Science et la Technologie, Consulat Général de France à Shanghai (RPC)
2008-2009 : Délégation CNRS, LIAMA, CNRS-INRIA-Académie des Sciences de Chine, Pékin
Depuis 2009 : Vice-Président délégué aux Relations Internationales, Université Bordeaux I


Page mise à jour le 13/08/2010 à 10:56