Sa thèse permet de montrer que les preuves circulaires ont un réel statut de preuve théorique et qu'elles peuvent être appliquées à d’autres domaines comme la vérification formelle.
En 2014, Amina Doumane bénéficie d'une bourse de la région Ile-de-France dans le cadre du domaine d'intérêt majeur « Recherche doctorale en mathématiques-IDF », rebaptisé depuis « DIM Math Innov »[3].
De 2014 à 2017, elle prépare sa thèse de Doctorat intitulée On the infinitary proof theory of logics with fixed points (Sur la théorie de la démonstration infinitaire pour les logiques à points fixes)[4], dirigée par David Baelde, Pierre-Louis Curien et Alexis Saurin à l'Université Paris Diderot.
Utilisées entre autres pour la vérification de programmes informatiques, les logiques infinitaires permettent des formules ou des démonstrations infiniment longues.
Le résultat obtenu concerne le « théorème de complétude ». Ce dernier dit que si une formule est vraie, alors elle est prouvable. L'Américain Dexter Kozen en 1983 puis Roope Kaivola[5] en 1995 avaient apporté une démonstration de ce théorème dans le cadre du µ-calcul[a], mais de manière non constructive, à savoir que l'on savait que la preuve existe mais on n'était pas en mesure de produire cette preuve.
Le travail d'Amina Doumane permet désormais de certifier qu'un système informatique répond bien aux exigences qui lui sont spécifiées, tout en produisant le certificat qui le prouve. « Le certificat est une expression mathématique, preuve de cette implication, que l'on peut communiquer à d'autres personnes qui, en plus, sauront pourquoi le système satisfait la propriété : le certificat a une vertu explicative » selon les mots de la chercheure.
Pour y parvenir, Amina Doumane a réussi à concevoir un algorithme qui permet à partir d'une formule de µ-calcul de construire automatiquement une preuve[6]. Cette formule de µ-calcul peut être la « grande implication » exprimant que le système (S) vérifie la propriété (P), à savoir que (S) ⇒ (P) est vrai. Pour obtenir la preuve constructive, elle décompose toute formule de µ-calcul en sous-formules intermédiaires, puis elle prouve chacune grâce à des preuves infinitaires. Enfin elle applique à chacune de ces preuves un algorithme qu'elle a mis au point permettant de transformer une preuve infinitaire en preuve usuelle[1]. La difficulté réside dans le choix des décompositions. Pour y parvenir, elle s'est inspirée de la théorie des automates qui offre des outils pour surmonter les difficultés que sont l'alternance (de ∧ et ∨), les conditions de parité (alternance de μ et ν) et le non-déterminisme (présence de ∨)[7].
Publications
On the infinitary proof theory of logics with fixed points, 2017, thèse soutenue à l’Université Paris Diderot (Paris 7) Sorbonne Paris Cité et préparée à l’Institut de Recherche en Informatique Fondamentale (IRIF) et au Laboratoire spécification et vérification (LSV) sous la direction de David Baelde, Alexis Saurin et Pierre-Louis Curien.
↑R. Kaivola démontre le théorème de complétude du μ-calcul : « Si une formule du μ-calcul est valide, alors elle est prouvable dans le système de Kozen ».
