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.

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: DOI