For , let denote , where is a polynomial in y with integer coefficients, and are linear polynomials in with integer coefficients. Let be a Presburger relation over the nonnegative integers. We show that the following problem is decidable:
Given: and a Presburger relation P.
Question: Are there nonnegative integer values for such that for these values, satisfies P?
We also give some applications to decision problems concerning counter machines.