Can I read Natural Proofs for Structure, Data, and Separation on EtoBox?

Natural Proofs for Structure, Data, and Separation by Xiaokang Qiu; Pranav Garg; Andrei Ştefănescu; Parthasarathy Madhusudan is a Computer Science article available to read on EtoBox.

What is Natural Proofs for Structure, Data, and Separation about?

We propose natural proofs for reasoning with programs that manipulate data-structures against specifications that describe the structure of the heap, the data stored within it, and separation and framing of sub-structures. Natural proofs are a subclass of proofs that are amenable to completely automated reasoning, that provide sound but incomplete procedures, and that capture common reasoning tactics in program verification. We develop a dialect of separation logic over heaps, called Dryad, with recursive definitions that avoids explicit quantification. We develop ways to reason with heaplets using classical logic over the theory of sets, and develop natural proofs for reasoning using proof tactics involving disciplined unfoldings and formula abstractions. Natural proofs are encoded into decidable theories of first-order logic so as to be discharged using SMT solvers. We also implement the technique and show that a large class of more than 100 correct programs that manipulate data-structures are amenable to full functional correctness using the proposed natural proof method. These programs are drawn from a variety of sources including standard data-structures, the Schorr-Waite algo

Who reads Natural Proofs for Structure, Data, and Separation?

Author

Xiaokang Qiu; Pranav Garg; Andrei Ştefănescu; Parthasarathy Madhusudan

Publisher

ACM

Published

2013

Language

EN

Field

Computer Science (Physical Sciences)