A criterion for eliminating unnecessary reductions in the Knuth-Bendix algorithm

1 August 1983

journal article
Published by Association for Computing Machinery (ACM) in ACM SIGSAM Bulletin

Vol. 17 (3-4) , 20
https://doi.org/10.1145/1089338.1089341

Abstract

Given a finite set E of multivariate polynomials, the second author's 1965 algorithm constructs a set E' of polynomials such that E and E' generate the same ideal congruence, but E' has the additional property that the congruence can be decided by "reduction to normal forms w.r.t. E'." The two essential ideas of this algorithm are: the consideration of certain "critical pairs" associated with elements in E and the successive "completion" of E by adjoining the difference of normal forms of critical pairs.

Keywords

CRITICAL PAIR
ADDITIONAL PROPERTY
UNNECESSARY REDUCTION
MULTIVARIATE POLYNOMIAL
FINITE SET E
NORMAL FORM
ALGORITHM CONSTRUCT
KNUTH-BENDIX ALGORITHM
ESSENTIAL IDEA
NORMAL FORMS W
IDEAL CONGRUENCE
SET E

This publication has 0 references indexed in Scilit: