Sur l'intégration des langages algébriques et logique

Ce mémoire présente l'étude d'une approche particulière des langages de programmation logico-fonctionnels, fondée sur la logique des clauses de Horn avec égalité. Nous définissons d'abord la syntaxe et la sémantique des programmes que nous considérons. La syntaxe est celle de la logique des clauses de Horn avec égalité. La sémantique est donnée par le plus petit e-modele de Herbrand associe a un programme. Nous nous intéressons ensuite au calcul dans ce langage. Nous proposons pour cela une nouvelle règle appelée sldei-resolution comme seule règle de calcul. Nous montrons sa cohérence, sa complétude ainsi que sa completude forte. La mise en œuvre de la règle sldei-resolution nécessite un algorithme de resolution d'équations. Nous étudions de tels algorithmes fondes sur la relation de surreduction, et améliorons ces algorithmes par l'utilisation de stratégies de surreduction. Cependant, ces stratégies ne sont pas complètes dans le cas général. Nous proposons alors des conditions suffisantes sur ces stratégies afin de préserver la complétude des algorithmes considérés. Nous caractérisons ensuite une classe de programmes, dits uniformes, pour lesquels l'utilisation de n'importe quelle stratégie de surreduction donne un algorithme complet de resolution d'équations. Nous donnons de plus une methode de vérification de l'uniformité d'un programme. Par ailleurs, nous proposons des conditions syntaxiques pour qu'un programme soit uniforme. Enfin, nous décrivons les principaux traits d'un langage de programmation fonde sur l'approche présentée dans ce mémoire, et l'implantation que nous avons réalisé