# zbMATH — the first resource for mathematics

Semigroup ideals and linear Diophantine equations. (English) Zbl 0939.20061
Let $$S$$ be a finitely generated commutative cancellative monoid, and let $$\{n_1,\dots,n_r\}\subset S$$ be a set of generators for $$S$$. Let $$k$$ be a field, $$R=k[S]$$ the associated semigroup $$k$$-algebra, $$R=k[X_1,\dots,X_r]$$ the polynomial ring, and $$\varphi\colon R\to k[S]$$ the $$k$$-algebra homomorphism given by $$\varphi(X_i)=n_i$$. The author gives a purely algebraic algorithm to calculate a finite set of generators for $$\ker\varphi$$. As an application, using Gröbner bases, an algorithm is given to determine whether a linear system of equations with integer coefficients having some of the equations in congruences admits non-negative integer solutions.

##### MSC:
 20M14 Commutative semigroups 20M05 Free semigroups, generators and relations, word problems 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) 11D04 Linear Diophantine equations 68W30 Symbolic computation and algebraic computation
Full Text: