Multiway Decision Graphs Reduction Approach based on the HOL Theorem Prover

Multiway Decision Graphs (MDGs) subsume Binary Decision Diagrams (BDDs) by representing formulae which are suitable for first-order model checking able to handle large datapath circuits. In this paper, we propose a reduction approach to improve MDGs model checking. We use a reduction platform based on combining MDGs with the rewriting engine of the HOL theorem prover. The idea is to prune the transition relation of the design using pre-proved theorems and lemmas from the specification given at system level. Then, the actual proof of temporal MDG formulae will be achieved by the MDGs model checker.