✍ Scribed by CLAUDE MARCHÉ
No coin nor oath required. For personal study only.
In the first part of this paper, we introduce normalized rewriting, a new rewrite relation. It generalizes former notions of rewriting modulo a set of equations E, dropping some conditions on E. For example, E can now be the theory of identity, idempotence, the theory of Abelian groups or the theory of commutative rings. We give a new completion algorithm for normalized rewriting. It contains as an instance the usual AC completion algorithm, but also the well-known Buchberger algorithm for computing Gröbner bases of polynomial ideals.
In the second part, 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 theories E. As a consequence, we obtain the decidability of the word problem for some classes of equational theories, including the AC-ground case (a result known since 1991), the ACUI-ground case (a new result to our knowledge), and the cases of ground equations modulo the theory of Abelian groups and commutative rings, which is already known when the signature contains only constants, but is new otherwise.
Finally, we give implementation results which show the efficiency of normalized completion with respect to completion modulo AC.
📜 SIMILAR VOLUMES
The isothermal crystallization of glycine in a 40/60 (w/w) sucrose/glycine excipient system is examined with the goal of comparing the kinetic information obtained by using the Johnson-Mehl-Avrami (JMA) equation with that collected using a novel, dispersive kinetic model equation recently proposed b