Skip to main content

Automatic cyclic termination proofs for recursive procedures in separation logic

Rowe, Reuben N.S. and Brotherston, James (2017) Automatic cyclic termination proofs for recursive procedures in separation logic. In: Proceedings of the 6th ACM SIGPLAN Conference on Certified Programs and Proofs. POPL Principles of Programming Languages . ACM, New York, USA, pp. 53-65. ISBN 978-1-4503-4705-1. (doi:10.1145/3018610.3018623) (KAR id:64716)

PDF Author's Accepted Manuscript
Language: English

Download (301kB) Preview
[thumbnail of cpp_2017.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


We describe a formal verification framework and tool implementation, based upon cyclic proofs, for certifying the safe termination of imperative pointer programs with recursive procedures. Our assertions are symbolic heaps in separation logic with user defined inductive predicates; we employ explicit approximations of these predicates as our termination measures. This enables us to extend cyclic proof to programs with procedures by relating these measures across the pre- and postconditions of procedure calls. We provide an implementation of our formal proof system in the Cyclist theorem proving framework, and evaluate its performance on a range of examples drawn from the literature on program termination. Our implementation extends the current state-of-the-art in cyclic proof-based program verification, enabling automatic termination proofs of a larger set of programs than previously possible.

Item Type: Book section
DOI/Identification number: 10.1145/3018610.3018623
Subjects: Q Science > QA Mathematics (inc Computing science)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Reuben Rowe
Date Deposited: 24 Nov 2017 13:30 UTC
Last Modified: 16 Feb 2021 13:50 UTC
Resource URI: (The current URI for this page, for reference purposes)
Rowe, Reuben N.S.:
  • Depositors only (login required):


Downloads per month over past year