À l'heure actuelle, le contrôle des ressources (temps ou espace) utilisées par un programme devient une nécessité. En effet, de plus en plus de programmes sont exécutés sur des machines distantes (code mobile, Javacards,...) et il est nécessaire de leur faire confiance. Savoir que le programme reçu vérifie certaines propriétés de bon comportement peut permettre d'éviter certaines attaques. L'utilisation des ressources (temps ou espace) est l'une de ces propriétés. En effet on peut ainsi assurer, par exemple, qu'un programme n'essayera pas d'écrire dans des zones mémoires réservées ou qu'une requête ne risque pas de bloquer un serveur.
Afin de contrôler ces ressources de manières automatique, je m'intéresse à la complexité des programmes. Ceux-ci sont modélisés à l'aide de systèmes de réécritures. Des techniques classiques (ordres de terminaison, interprétations polynomiales) permettent d'assurer la terminaison du système de réécriture mais ne donnent aucune information sur sa complexité (ou du moins aucune information utilisable facilement). L'analyse prédicative résout ses problèmes en introduisant une notion de niveau (« tier »). On génère ainsi des ordres de terminaison « allégés » qui capturent les classes de complexité Ptime ou Pspace. Malheureusement, ces ordres ne parviennent pas à analyser beaucoup d'algorithmes « naturels ».
Pour compenser ce problème, nous avons introduit la notion de quasi-interprétation polynomiales. Elles ne suffisent pas à prouver la terminaison du programme, mais permettent de contrôler la taille des termes intermédiaires obtenus lors du calcul. En les couplant avec les ordres de terminaison, on obtient de nouveau une caractérisation de Ptime et Pspace mais en capturant cette fois-ci beaucoup plus d'algorithmes naturels.
De plus, cette caractérisation porte sur la complexité implicite du programme, c'est-à-dire sur la complexité de la fonction calculée, et non sur sa complexité explicite (c'est-à-dire la complexité de l'algorithme lui-même, qui peut être beaucoup plus élevée). Afin d'atteindre la borne polynomiale, il est parfois nécessaire de transformer l'algorithme aux moyens de techniques de mémoïzation.
Je présenterais aussi Icar, un logiciel qui regroupe les résultats exposés et permet donc d'analyser les programmes et de les transformer en cas de besoins pour obtenir la borne polynomiale.
Les résultats présentés se trouvent, entre autre, dans les chapitres 3, 4 et 5 de ma thèse où des références vers plus de bibliographie peuvent être trouvées.