Skip to Main content Skip to Navigation
Reports

Investigations on termination of equational rewriting

Abstract : 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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00075820
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 7:05:54 PM
Last modification on : Thursday, February 11, 2021 - 2:48:31 PM
Long-term archiving on: : Friday, May 13, 2011 - 3:30:44 PM

Identifiers

  • HAL Id : inria-00075820, version 1

Collections

Citation

Isabelle Gnaedig. Investigations on termination of equational rewriting. [Research Report] RR-0732, INRIA. 1987. ⟨inria-00075820⟩

Share

Metrics

Record views

92

Files downloads

71