Décision des problèmes de compléments associatifs-commutatifs - Université de Lorraine Accéder directement au contenu
Thèse Année : 1995

Decision of associative-commutative complement problems

Décision des problèmes de compléments associatifs-commutatifs

Jean-Luc Moysset
  • Fonction : Auteur
  • PersonId : 756546
  • IdRef : 192597930

Résumé

Not available
La décision du problème de compléments AC, à partir d'un terme T et d'un ensemble de termes S1, Sn, consiste à vérifier s'il existe une AC-instance close de t qui ne soit couverte par aucune des AC-instances closes des termes S1,, Sn. Nous décrivons deux approches du problème: l'une de type descendante utilisant le principe des arbres de motifs introduit par e. Kounalis, l'autre de type ascendante, s'appuyant sur la réalisation d'automates ascendant d'arbres avec conditions ayant de bonnes propriétés. La décision du problème de compléments AC général reste néanmoins un problème ouvert et les deux méthodes présentées permettent de décider d'un certain nombre de cas non-linéaires ou en particulier les termes du problème peuvent avoir des occurrences multiples de variables que sous un même symbole de fonction (AC ou non). Des extensions du problème à d'autres théories (AC1, ACI) sont possibles ainsi que la décision de problèmes similaires tels que la propriété de réductibilité inductive modulo AC
Fichier non déposé

Dates et versions

tel-01753765 , version 1 (29-03-2018)

Identifiants

  • HAL Id : tel-01753765 , version 1

Accès intranet

Citer

Jean-Luc Moysset. Décision des problèmes de compléments associatifs-commutatifs. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 1995. Français. ⟨NNT : 1995NAN10238⟩. ⟨tel-01753765⟩
11 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More