This HTML5 document contains 28 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

n2:id

rdf:type

rdac:C10001 frbr:Work

marcrel:ths

n18:id n19:id

marcrel:aut

n15:id

skos:altLabel

Decision of associative-commutative complement problems

dc:subject

Compilation (informatique) Complétude Automates Automate Problème complémentarité Théorie automate Thèses et écrits académiques Compilation Complétude, Théorème de

skos:prefLabel

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

dcterms:language

n7:fra

dcterms:subject

n6:id n8:id n11:id n20:id

dc:title

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

marcrel:dgg

n13:id

skos:note

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

dc:type

Text

n21:P1001

n22:T1009

rdaw:P10219

1995

rdau:P60049

n10:1020