Spelling suggestions: "subject:"ecriture conditionnelle"" "subject:"ecriture konditionelle""
1 |
E-unification en demonstration automatiqueDelsart, Bertrand 22 November 1994 (has links) (PDF)
Depuis les travaux de Martelli et Montanari en 1982, la resolution de problemes de E-unification s'effectue souvent par transformation de systemes d'equations. L'objectif de cette these est de presenter des nouvelles regles de transformations qui de- crivent de facon unifiee comment appliquer des axiomes a la ra- cine des termes. Les proprietes theoriques de ces regles sont etablies (correction, completude...). Nous prouvons egalement que cette approche, basee sur la notion de presentations strictement resolventes, est plus generale que des algorithmes tres connus (Root-Rewriting [J. Gallier & W. Snyder ], Mutation Syntaxique [C. Kirchner ]). Une analyse du comportement de ces regles per- met d'etablir l'inter^et de l'application d'axiomes a la racine et de definir le type de presentations strictement resolventes qui devraient fournir les meilleurs resultats. Ces presentations sont generees automatiquement. Pour ce faire, nous introduisons la notion de completion strictement resolvente. Elle permet de definir les proprietes theoriques des regles de completion donnees. Differentes strategies sont etu- diees, allant d'une strategie qui termine toujours a la strategie (parfois divergente) conduisant a une presentation tres efficace. Des recherches theoriques peuvent s'effectuer dans ce (nouveau) formalisme general. Elles s'appliquent aux algorithmes subsumes par cette approche. Par exemple, les avantages vis a vis du parallelisme sont etablis et conduisent a une presentation compacte de l'ensemble des unificateurs. Des optimisations theoriques plus complexes sont egalement etudiees. La detection des instanciations inutiles des variables lors de l'unification d'un terme avec les t^etes de regles est la plus importante. Elle permet d'etablir la completude des solutions donnees pour un probleme m^eme si la presentation n'est pas strictement resol- vente (completion divergente). Les resultats experimentaux mettent en valeur la simplicite et la generalite de cette nouvelle approche. Sa generalite permet egalement de comparer les differents algorithmes et de justifier l'utilisation de la strategie non complete de generation des re- gles. L'etude de cas particuliers montre que l'on peut ainsi ob- tenir des resultats tres interessants en un temps tout a fait raisonnable. On peut donc envisager d'utiliser ce module de E- unification au sein d'un demonstrateur.
|
Page generated in 0.1262 seconds