Invariants algébriques des systèmes informatiques – INVAL

Le but de ce projet est de prolonger un des thèmes qui est apparu primordial lors de l'action spécifique CNRS Topologie Algébrique pour l'étude des structures de calcul et notamment de la concurrence (voir www.di.ens.fr/~goubault/asreport.pdf). Plusieurs équipes dans cette AS ont en effet développé des méthodes algébriques proches, visant à la description des structures de calcul (pour les systèmes de réécriture, le calcul parallèle, certaines formes de lambda-calcul etc.) que l'on voudrait faire converger dans ce projet. L'idée principale est de caractériser l'expressivité d'un paradigme de calcul en lui associant un invariant algébrique, tel que, par exemple, un type d'homotopie, ou de préférence, pour des raisons de calculabilité, un type d'homologie. Ces invariants à leur tour permettent de résoudre certains problèmes, d'analyse statique par exemple (réduction de l'explosion combinatoire lors de la validation de programmes parallèles). On souhaite dans ce projet développer notablement ces méthodes, grâce à une collaboration étroite entre des équipes de mathématiciens (topologie algébrique et algèbre homologique) et des équipes d'informaticiens.