This paper gives an exact characterization of conditional termination for a class of nondeterministic homogeneous integer equality relations over nonnegative integer coefficient vectors.
The central result identifies precisely when the descending predecessor sequence reaches the weakest nontermination precondition after finitely many steps. Under pointedness of the source cone, nonzero source generators and cone-monotone displacement, finite convergence occurs if and only if the canonical deterministic quotient associated with every closed face is integral over the integers. Equivalently, every closed-face quotient must have an integer characteristic polynomial.
The proof separates the problem into three structural layers. On closed faces, continuation lattices stabilize exactly when an integral serial lattice exists, which is equivalent to integrality of the deterministic quotient. Nonclosed faces are handled by automatic ascent through the face map until a closed face is reached. Deep-rescue arguments and a finite-tube induction then convert these local arithmetic conditions into a global uniform bound on mortality depth.
The theorem is effective. The closed faces can be enumerated, their deterministic quotients computed by exact rational linear algebra, and the integrality condition checked directly. When the criterion holds, repeated Presburger predecessor computation eventually produces the exact weakest nontermination precondition.
The paper also develops a quantitative theory of convergence. For a closed face with integral serial lattice K, the continuation-lattice filtration stabilizes after at most the base-2 logarithm of the lattice index. Propagating conductor, residue and tube bounds through the proof gives a computable global upper bound on predecessor convergence. Conversely, an explicit fixed-dimensional family has exact mortal depth m + 1 and shows that predecessor convergence can grow exponentially in the binary input length even when the deterministic quotient is trivial.
The resulting class is distinct from previously known exact conditional-termination classes such as octagonal relations and finite-monoid affine systems. It permits genuinely nondeterministic relations, arbitrary physical dimension and infinite ambient matrix monoids. The paper also places the result within the wider literature on linear-constraint loops, affine counter systems and deterministic linear-loop termination.
Two geometric figures illustrate the closed-face mechanism and the finite-tube induction. A companion exact-arithmetic verification package reproduces the principal examples, the long-transient family and the exhaustive small-system computational checks reported in the paper.
Topics: conditional termination, weakest nontermination preconditions, integer equality relations, affine semigroups, cone monotonicity, closed faces, lattice stabilization, Presburger arithmetic, nondeterministic systems and termination analysis.
Leave a Reply