On the solvability of a class of diophantine equations and applications

For 1⩽i⩽k, let Ri denote pi(y)Fi+Gi, where pi(y) is a polynomial in y with integer coefficients, and Fi,Gi are linear polynomials in x1,…,xn with integer coefficients. Let P(z1,…,zk) be a Presburger relation over the nonnegative integers. We show that the following problem is decidable:Given: R1,…,Rk and a Presburger relation P.Question: Are there nonnegative integer values for y,x1,…,xn such that for these values, (R1,…,Rk) satisfies P?We also give some applications to decision problems concerning counter machines.