On the solvability of a class of Diophantine equations and applications (Q818150)

For \(1\leq i\leq k\), let \(R_i\) denote \(p_i(y)F_i+G_i\), where \(p_i(y)\) is a polynomial in \(y\) with integer coefficients, and \(F_i, G_i\), are linear polynomials in \(x_1, \dots,x_n\) with integer coefficients. Let \(P(z_1,\dots,z_k)\) be a Presburger relation over the nonnegative integers. It is shown that the following problem is decidable: Given: \(R_1,\dots,R_k\) and a Presburger relation \(P\). Question: Are there nonnegative integer values for \(y, x_1,\dots,x_n\) such that for these values, \((R_1,\ldots,R_k)\) satisfies \(P\)? Some applications to decision problems concerning counter machines are also presented.