Axiomatic Basis for Computer Programming
By L. Osho, F. Ogwueleka, Oluwafemi Osho. 2013
993 citations recorded by the source corpus.
This paper considers a formal method, known as axiomatic semantics, used to prove the correctness of a computer program. This formal method extracts, using some proof rules, the mathematical verification conditions from a computer program. The axioms of program flow, including, sequential flow, iteration, and alternation flows are presented. Using the axiomatic basis the completeness of two variants of integer multiplication program is proved. Results show that computer programs can actually be verified sufficiently for correctness without necessarily testing them, or more practically put, to complement their testing.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Model Architectures, Program Analysis & Verification
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Marc Brockschmidt
- Yoshua Bengio
- Daniel Kifer
- Percy Liang
- Mohit Bansal
- Quoc V. Le
- Ruslan Salakhutdinov
- Justin Hsu
In Computational Theory and Mathematics
- Srinath T. V. Setty
- Jon Howell
- Bryan Parno
- Gilles Barthe
- Muzammil Shahbaz
- Shin Yoo
- Mark Harman
- Aaron Roth
In Model Architectures
- Shin Yoo
- Daniel Tarlow
- Earl T. Barr
- Bernhard Beckert
- Richard S. Zemel
- Marc Brockschmidt
- Jonathan Huang
- Suman Sekhar Jana
In Program Analysis & Verification
- Srinath T. V. Setty
- Marc Brockschmidt
- Bryan Parno
- Jon Howell
- Shin Yoo
- Gilles Barthe
- Mark Harman
- Daniel Tarlow
Citations in the corpus
- Gated Graph Sequence Neural Networks (2015, methodology): “Using it, we can prove that no program run will fail due to dereferencing an unallocated memory address (this property is called memory safety ) and that the function indeed concatenates two lists using a Hoare-style verification scheme (Hoare, 1969).”
- Deductive Software Verification – The KeY Book (2016, methodology): “course, we wanted to illustrate formal verification in Hoare style [Hoare, 1969], and with a simple while-language, not Java.”
- Learning Program Embeddings to Propagate Feedback on Student Code (2015, methodology): “We propose to learn program features using a training set of E n c od e r ( P, A, Q ) -triples — so-called Hoare triples (Hoare, 1969) obtained via historical runs of a collection of programs on a collection of preconditions.”
- CLN2INV: Learning Loop Invariants with Continuous Logic Networks (2019, background): “Given a loop, while(LC){C}, a precondition P , and a postcondition Q, the verification task involves finding a loop invariant I that can be concluded from the precondition and implies the post-condition (Hoare, 1969).”
- The Oracle Problem in Software Testing: A Survey (2015, methodology): “Assertions gained significant attention as a means of capturing language semantics in the seminal work of Floyd [64] and Hoare [94] and subsequently were championed as a means of increasing code quality in the development of the contract-based programming approach, notably in the language Eiffel [13”
- Computer-Aided Verification for Mechanism Design (2015, methodology): “Finally, RSM runs the well-known Vickrey-Clarke-Groves mechanism [26, 9, 15] to match each replica with a surrogate in this market.”
- IronFleet: proving practical distributed systems correct (2015, methodology): “Many program verification tools support Floyd-Hoare style [17, 22] first-order predicate logic reasoning about imperative programs.”