Mai Gehrke, ERC Advanced Grant 2014

Pour apprendre, certaines personnes mémorisent mieux en voyant et d’autres en écoutant. Cela ne signifie pas qu’il faille leur apprendre des choses différentes, mais plutôt qu’il peut y avoir deux façons d’approcher un même sujet. La dualité exploite le principe de mise en parallèle en associant deux points de vue, ce qui permet de créer une synergie très intéressante : un problème qui serait difficile dans un contexte peut être résolu dans l’autre, et la solution peut être retraduite dans le premier contexte. Le point de départ de l’ERC DuaLL est l’utilisation de la dualité de Stone, résultat mathématique de 1936, pour mettre en regard deux domaines des mathématiques a priori totalement éloignés : les langages réguliers, reconnus par des automates finis, qui forment le modèle de machine le plus élémentaire possible ; et les espaces topologiques compacts, objets mathématiques abstraits aux propriétés importantes. Dans un article de 2008, Mai Gehrke et ses coauteurs, Serge Grigorieff et Jean-Éric Pin, ont montré que la dualité de Stone fournissait un cadre très puissant pour l’étude des langages réguliers. Mai Gehrke souhaite aller plus loin, au-delà des automates finis. En particulier, l’un des challenges est l’étude des circuits booléens, et notamment de savoir si une classe de circuits est plus puissante qu’une autre. Elle souhaite aussi généraliser la méthode à d’autres classes d’automates, par exemple les automates de coût qui permettent de modéliser les problèmes de maximisation des gains. 

Un autre objectif est la recherche d’extensions robustes de la théorie des langages réguliers. Un outil puissant pour classifier les langages réguliers et fournir des résultats de décidabilité est la théorie d’Eilenberg-Reiterman qui peut être vue comme un cas particulier de la dualité de Stone sur les algèbres booléennes avec opérateurs. La volonté est ici d’étendre le cadre à n’importe quel langage, ce qui implique de se placer sur des espaces extrêmement compliqués (l’un se nomme par exemple « the three-headed monster » !). Il s’agit d’étudier des classes beaucoup plus abstraites, sur lesquelles il y a très peu de connaissances, mais où justement la dualité pourrait apporter un éclairage nouveau. Dans le processus de recherche, il faudra dans un premier temps « re-prouver », dans un cadre plus général, les résultats connus en appliquant le principe de dualité, ce qui sera déjà laborieux puisque les techniques utilisées jusque-là sont assez éloignées. 

Enfin, le dernier objectif du projet concerne la sémantique formelle des langages de programmation, qui permet, en informatique théorique, d’étudier la signification des programmes informatiques vus en tant qu’objets mathématiques. La dualité de Stone est depuis longtemps un outil central et très performant en sémantique, mais Mai Gehrke souhaite appliquer les résultats de la théorie des automates, dans leurs variantes plus abstraites de la dualité de Stone, pour étudier certains problèmes de modélisation réputés difficiles, comme le traitement des quantificateurs.