Skip to Main content Skip to Navigation
Theses

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

Résumé : 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
Document type :
Theses
File URL :
http://docnum.univ-lorraine.fr/prive/SCD_T_1995_0238_MOYSSET.pdf
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01753765
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 4:48:23 PM
Last modification on : Tuesday, January 29, 2019 - 1:21:54 AM

Identifiers

  • HAL Id : tel-01753765, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

4