Omn.Pres.Franc.- Analyse de la Propriété d'Incrémentalité Du Programme de Branchement Propriété inventée pour la résolution du problème GEN par un programme de branchement

Ce memoire est consacre principalement a l'etude des programmes de branchement incrementaux. Le programme de branchement est un modele de calcul qui capture la quantite de memoire requise a la resolution d'un probleme calculatoire. Afin de capturer une facon naturelle de construire un programme de branchement resolvant GEN (un probleme P-complet), la restriction d'incrementalite a ete inventee. Dans ce memoire, nous proposons principalement une methode pour transformer un certain type de programme de branchement en un programme entierement syntaxique incremental. Nous prouvons aussi que de determiner s'il existe un chemin incremental dans un programme de branchement est NP-complet."