Entire DC Network | Open Access Articles | Digital Commons Network™

Complete Sets Of Reductions Modulo A Class Of Equational Theories Which Generate Infinite Congruence Classes, Timothy B. Baird, Ralph W. Wilkerson Jul 1988

Complete Sets Of Reductions Modulo A Class Of Equational Theories Which Generate Infinite Congruence Classes, Timothy B. Baird, Ralph W. Wilkerson

Computer Science Technical Reports

In this paper we present a generalization of the Knuth-Bendix procedure for generating a complete set of reductions modulo an equational theory. Previous such completion procedures have been restricted to equational theories which generate finite congruence classes. The distinguishing feature of this work is that we are able to generate complete sets of reductions for some equational theories which generate infinite congruence classes. In particular, we are able to handle the class of equational theories which contain the associative, commutative, and identity laws for one or more operators.

We first generalize the notion of rewriting modulo an equational theory to …

Go to article

Complete Sets Of Reductions Modulo A Class Of Equational Theories Which Generate Infinite Congruence Classes, Timothy B. Baird Jan 1988

Complete Sets Of Reductions Modulo A Class Of Equational Theories Which Generate Infinite Congruence Classes, Timothy B. Baird

Doctoral Dissertations

"In this paper we present a generalization of the Knuth-Bendix procedure for generating a complete set of reductions modulo an equational theory. Previous such completion procedures have been restricted to equational theories which generate finite congruence classes. The distinguishing feature of this work is that we are able to generate complete sets of reductions for some equational theories which generate infinite congruence classes. In particular, we are able to handle the class of equational theories which contain the associative, commutative, and identity laws for one or more operators.