Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T21:07:59.792Z Has data issue: false hasContentIssue false

Programming Combinations of Deduction and BDD-based Symbolic Calculation

Published online by Cambridge University Press:  01 February 2010

Michael J. C. Gordon
Affiliation:
University of Cambridge Computer Laboratory, New Museums Site, William Gates Building, J. J. Thomson Avenue, Cambridge CB3 0FD, mjcg@cl.cam.ac.uk, http://www.cl.cam.ac.uk/~mjcg

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A generalisation of Milner's ‘LCF approach’ is described. This allows algorithms based on binary decision diagrams (BDDs) to be programmed as derived proof rules in a calculus of representation judgements. The derivation of representation judgements becomes an LCF-style proof by defining an abstract type for judgements analogous to the LCF type of theorems. The primitive inference rules for representation judgements correspond to the operations provided by an efficient BDD package coded in C (BuDDy). Proof can combine traditional inference with steps inferring representation judgements. The resulting system provides a platform to support a tight and principled integration of theorem proving and model checking. The methods are illustrated by using them to solve all instances of a generalised Missionaries and Cannibals problem.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2002