Unification in Commutative Theories, Hilbert's Basis Theorem, and Gröbner Bases

Abstract

Unification in a commutative theory E may be reduced to solving linear equations in the corresponding semiring S(E) (Nutt (1988)). The unification type of E can thus be characterized by algebraic properties of S(E). The theory of abelian groups with n commuting homomorphisms corresponds to the semiring Z[X1,...,Xn]. Thus Hilbert’s Basis Theorem can be used to show that this theory is unitary. But this argument does not yield a unification algorithm. Linear equations in Z[X1,..,Xn] can be solved with the help of Gröbner Base methods, which thus provide the desired algorithm. The theory of abelian monoids with a homomorphism is of type zero (Baader (1988)). This can also be proved by using the fact that the corresponding semiring, namely N[X], is not noetherian. An other example of a semiring (even ring), which is not noetherian, is the ring Z<X1,...,Xn>, where X1, ..., Xn ( n > 1 ) are non-commuting indeterminates. This semiring corresponds to the theory of abelian groups with n non-commuting homomorphisms. Surprisingly, by construction of a Gröbner Base algorithm for right ideals in Z<X1,...,Xn>, it can be shown that this theory is unitary unifying.