Gröbner bases and their application to the Cauchy problem on finitely generated affine monoids

For finitely generated submonoids of the integer lattice and submodules over the associated monoid algebra, we investigate Gröbner bases with respect to generalised term orders. Up to now, this theory suffered two disadvantages: The algorithm for computing the Gröbner bases was slow and it was not known whether there existed generalised term orders for arbitrary finitely generated submonoids. This limited the applicability of the theory. Here, we describe an algorithm which transports the problem of computing the Gröbner bases to one over a polynomial ring and use the conventional Gröbner theory to solve it, thus making it possible to apply known, optimised algorithms to it. Furthermore, we construct generalised term orders for arbitrary finitely generated submonoids. As an application we solve the Cauchy problem (initial value problem) for systems of linear partial difference equations over finitely generated submonoids.