The strength of SCT soundness

Abstract

In this paper we continue the study, from Frittaion, Steila and Yokoyama (2017), on size-change termination in the context of Reverse Mathematics. We analyze the soundness of the SCT method. In particular, we prove that the statement "any program which satisfies the combinatorial condition provided by the SCT criterion is terminating" is equivalent to $\mathrm{WO}({\omega }_3)$ over $\mathsf{RC}{\mathsf{A}}_0$

30 pages

References in corpus (1)

• Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma