In this paper we introduce a class of constraint logic programs such that their termination can be proved by using affine level mappings. We show that membership to this class is decidable in polynomial time.
Similarly to @cite_1 , Podelski and Rybalchenko have considered programs with no nested loops and no branching inside a loop. However, they focused on integer programs and provide a polynomial time decidability technique for a subclass of such programs. In case of general programs their technique can be applied to provide a sufficient condition for liveness.
@cite_1
1575647584
We show that termination of a class of linear loop programs is decidable. Linear loop programs are discrete-time linear systems with a loop condition governing termination, that is, a while loop with linear assignments. We relate the termination of such a simple loop, on all initial values, to the eigenvectors corresponding to only the positive real eigenvalues of the matrix defining the loop assignments. This characterization of termination is reminiscent of the famous stability theorems in control theory that characterize stability in terms of eigenvalues.