A pseudo-polynomial algorithm for the Frobenius number and Grobner basis

Given n ? 2 and a1, ... , an & ISIN; N. Let S = (a1, ... , an) be a semigroup. The aim of this paper is to give an effective pseudopolynomial algorithm on a1, which computes the Apery set and the Frobenius number of S. We also find the Grobner basis of the toric ideal defined by S, for the weighted degree reverse lexicographical order ≺w to x1, ..., xn, without using Buchberger's algorithm. As an application we introduce and study some special classes of semigroups. Namely, when S is generated by generalized arithmetic progressions and generalized almost arithmetic progressions with the ratio a positive or a negative number. We determine symmetric and almost symmetric semigroups generated by a generalized arithmetic progression.& COPY; 2023 Elsevier Ltd. All rights reserved.

Automated summary

The aim of this paper is to provide an effective pseudopolynomial algorithm on a1, which computes the Apery set and the Frobenius number of S. We also find the Grobner basis of the toric ideal defined by S without using Buchberger's algorithm. As an application, special classes of semigroups generated by generalized arithmetic progressions and generalized almost arithmetic progressions are introduced and studied.