Semigroup ideals and linear Diophantine equations. (English) Zbl 0939.20061

Vigneron-Tenorio, A.

Linear Algebra Appl. 295, No. 1-3, 133-144 (1999).

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.

Reviewer: David F.Anderson (Knoxville)

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

Keywords:

finitely generated commutative cancellative monoids; generators; semigroup algebras; algorithms; Gröbner bases; linear systems of equations