New Difference Gröbner Bases and Bivariate Difference Dimension Polynomials

We introduce a new type of Gröbner bases in free difference modules that are associated with a reduction respecting the effective order of module elements. We prove some properties of such Gröbner bases and present a Buchberger-type algorithm for their computation. Using the obtained results, we prove the existence and give a method of computation of a bivariate dimension polynomial of a finitely generated difference module that carries more module invariants than the classical difference dimension polynomial. We also show how the new invariants can be applied to the isomorphism problem for difference modules and to the equivalence problem for systems of algebraic difference equations.