On automated program construction and verification. (English)
Bolduc, Claude (ed.) et al., Mathematics of program construction. 10th international conference, MPC 2010, Québec City, Canada, June 21‒23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13320-6/pbk). Lecture Notes in Computer Science 6120, 22-41 (2010).
Summary: A new approach for automating the construction and verification of imperative programs is presented. Based on the standard methods of Floyd, Dijkstra, Gries and Hoare, it supports proof and refutation games with automated theorem provers, model search tools and computer algebra systems combined with “hidden” domain-specific algebraic theories that have been designed and optimised for automation. The feasibility of this approach is demonstrated through fully automated correctness proofs of some classical algorithms: Warshall’s transitive closure algorithm, reachability algorithms for digraphs, and Szpilrajn’s algorithm for linear extensions of partial orders. Sophisticated mathematical methods that have been developed over decades could thus be integrated into push-button engineering technology.