Reverse mathematical bounds for the termination theorem

DOI10.1016/j.apal.2016.06.001zbMath1402.03023arXiv1512.08622OpenAlexW2963942212MaRDI QIDQ324248

Silvia Steila, Keita Yokoyama

Publication date: 10 October 2016

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.08622

zbMATH Keywords

reverse mathematicsRamsey's theoremParis Harrington's theoremtermination theorem

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Second- and higher-order arithmetic and fragments (03F35)

Related Items (5)

The proof-theoretic strength of Ramsey's theorem for pairs and two colors ⋮ Partial Orders and Immunity in Reverse Mathematics ⋮ The Strength of the SCT Criterion ⋮ A Combinatorial Bound for a Restricted Form of the Termination Theorem ⋮ Dickson's lemma and weak Ramsey theory

Cites Work

• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• An intuitionistic version of Ramsey's theorem and its use in program termination
• Rapidly growing Ramsey functions
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• Proof-theoretic analysis of termination proofs
• Reverse mathematics and Peano categoricity
• Parameter free induction and provably total computable functions
• The strength of infinitary Ramseyan principles can be accessed by their densities
• The theory of well-quasi-ordering: a frequently discovered concept
• Measure theory and weak König's lemma
• On the strength of Ramsey's theorem for pairs
• Decidability of Termination of Grid String Rewriting Rules
• RT₂² does not imply WKL₀
• Stop When You Are Almost-Full
• Ramsey Theorem for Pairs As a Classical Principle in Intuitionistic Arithmetic
• Transition Invariants and Transition Predicate Abstraction for Program Termination
• Slicing the Truth
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Some independence results for Peano arithmetic
• On the Ramseyan Factorization Theorem
• An analysis of the Podelski–Rybalchenko termination theorem via bar recursion
• SEPARATING PRINCIPLES BELOW RAMSEY'S THEOREM FOR PAIRS
• Hierarchies of number-theoretic functions. I
• Ramsey's theorem and recursion theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reverse mathematical bounds for the termination theorem