×

An ideal-theoretical approach to word problems and unification problems over finitely presented commutative algebras. (English) Zbl 0581.68039

Rewriting techniques and applications, 1st Int. Conf., Dijon/France 1985, Lect. Notes Comput. Sci. 202, 345-364 (1985).
[For the entire collection see Zbl 0568.00022.]
A new approach based on computing the Gröbner basis of polynomial ideals is developed for solving word problems and unification problems for finitely presented commutative algebras. This approach is simpler and more efficient than the approaches based on generalizations of the Knuth- Bendix completion procedure to handle associative and commutative operators. It is shown that (i) the word problem over a finitely presented commutative ring with unity is equivalent to the polynomial equivalence problem modulo a polynomial ideal over the integers, (ii) the unification problem for linear forms is decidable for finitely presented commutative rings with unity, (iii) the word problem and unification problem for finitely presented boolean polynomial rings are co-NP- complete and co-NP-hard respectively, and (iv) the set of all unifiers of two forms over a finitely presented abelian group can be computed in polynomial time. Examples and results of algorithms based on the Gröbner basis computation are also reported.

MSC:

68W30 Symbolic computation and algebraic computation
03D40 Word problems, etc. in computability and recursion theory
13F20 Polynomial rings and ideals; rings of integer-valued polynomials
13E15 Commutative rings and modules of finite generation or presentation; number of generators
13L05 Applications of logic to commutative algebra

Citations:

Zbl 0568.00022