Investigations on termination of equational rewriting - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1987

Investigations on termination of equational rewriting

Isabelle Gnaedig

Résumé

This paper is a report of detailed investigations on the termination problem of rewriting modulo equational theories. We present here three approachs of this problem. We point out the difficulties and explain how the methods fail, giving some ideas issued from a rigorous observation of the failing processes. The first part is a new approach of the classical associative commutative (AC in short) orderings using the cooperation on abstract relations. We point out this proof method is not easy, because of an infinity of critical pairs to be considered. The second work consists in adapting the AC orderings with flattening to ensure termination modulo a large class of permutative theories. But the characterization of this class points out nothing other than the theories included in AC, for which the AC termination methods can be used. So we deduce, AC is the maximal class working with flattening. In the third chapter of this report, we propose a new AC ordering, replacing both flatening and distributing transformations by a single powerful transformation. We exhibit a counter-example to show that this method does not provide an F-compatible ordering.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-0732.pdf (902.2 Ko) Télécharger le fichier

Dates et versions

inria-00075820 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00075820 , version 1

Citer

Isabelle Gnaedig. Investigations on termination of equational rewriting. [Research Report] RR-0732, INRIA. 1987. ⟨inria-00075820⟩
37 Consultations
26 Téléchargements

Partager

Gmail Facebook X LinkedIn More