Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révision Les deux révisions suivantes | ||
fr:research:projects [2018/03/29 17:18] apeiron |
fr:research:projects [2018/03/29 17:21] apeiron |
||
---|---|---|---|
Ligne 12: | Ligne 12: | ||
====== Projets de recherche ====== | ====== Projets de recherche ====== | ||
+ | |||
+ | ===== Equivalence algorithmique en PLoopC et LPL ===== | ||
+ | |||
+ | Le langage LPL de Patrick Baillot, Marco Gaboardi et Virgile Mogbil est un langage de programmation fonctionnel, qui est en temps polynomial en s'assurant syntaxiquement de la réduction des termes dans les définitions, et en contraignant la récursion par un système de type issu de la logique linéaire. | ||
+ | |||
+ | Ce langage possède des caractéristiques proches de notre langage PLoopC comme l'utilisation de fonctions de base pour écrire les algorithmes (approche oraculaire) et des schémas de récursion syntaxiquement très souples, qui lui permettent notamment d'obtenir le minimum de Colson. Aussi, Pierre Valarcher et moi soupçonnons qu'il soit possible de prouver l'équivalence algorithmique entre LPL et la future version fonctionnelle de notre langage PLoopC. | ||
+ | |||
+ | Cela permettrait de faire un pont entre la communauté de la **complexité implicite** et la communauté de la **complexité par typage,** tout en fournissant une paire de langages capables de mettre fin à la quête d'un langage caractérisant les algorithmes polynomiaux. | ||