A k-system consists of k quadratic Diophantine equations over nonnegative integer variables s 1 ,...,s m , t 1 ,...,t n of the form: Σ B 1j (t 1 ,...,t n )A 1j (s 1 ,...,s m ) = C 1 (s 1 ,...,s m ) ΣB kj (t 1 ,...,t n )A kj (s 1 ,...,s m ) = C k (s 1 ,...,s m ) where l, n, m are positive integers, the B's are nonnegative linear polynomials over t 1 ,...,t n  (i.e., they are of the form b 0 +b 1 t 1 +...+b n t n , where each b i  is a nonnegative integer), and the A's and C's are nonnegative linear polynomials over s 1 ,...,s m . We show that it is decidable to determine, given any 2-system, whether it has a solution in s 1 , s m , t 1 ,...,t n , and give applications of this result to some interesting problems in verification of infinite-state systems. The general problem is undecidable; in fact, there is a fixed k > 2 for which the k-system problem is undecidable. However, certain special cases are decidable and these, too, have applications to verification.
['Gaoyan Xie', 'Zhe Dang', 'Oscar H. Ibarra']
A solvable class of quadratic Diophantine equations with applications to verification of infinite-state systems