A High Level Reachability Analysis using Multiway Decision Graph in the HOL Theorem Prover
Sa’ed Abed, Otmane Aı̈t Mohamed, Ghiath Al Sammane · 2007
In this paper, we provide all the necessary infrastructure to define a high level states exploration approach within the HOL theorem prover. While related work has tackled the same problem by representing primitive BDD operations as inference rules added to the core of the theorem prover, we have based our approach on the Multiway Decision Graphs (MDGs). We define canonic MDGs as well-formed directed formulae in HOL. Then, we formalize the basic MDG operations following a deep embedding approach and we derive the correctness proof for each operation. Finally, a high level reachability analysis is implemented as a tactic that uses our MDG theory within HOL.