Normalised rewriting and normalised completion

Publisher Website
Google Scholar
Abstract
Introduces normalised rewriting, a new rewrite relation. It generalises former notions of rewriting modulo E, dropping some conditions on E. For example, E can now be the theory of identity, idempotency, the theory of Abelian groups, or the theory of commutative rings. We give a new completion algorithm for normalised rewriting. It contains as an instance the usual AC completion algorithm (AC being the set of equations containing the associativity and commutativity axioms), but also the well-known Buchberger's algorithm for computing standard bases of polynomial ideals. We investigate the particular case of completion of ground equations. In this case, we prove by a uniform method that completion modulo E terminates, for some interesting E. As a consequence, we obtain the decidability of the word problem for some classes of equational theories. We give implementation results which show the efficiency of normalised completion with respect to completion modulo AC.

This publication has 23 references indexed in Scilit: