Mhamdi, Tarek (2003) On the embedding of multiway decision graphs in HOL. Masters thesis, Concordia University.
The increasing complexity of hardware systems requires more and more sophisticated methods of verification. While model checking suffers from the state space explosion problem, theorem proving is quite tedious and impractical for verifying complex designs. In this thesis, we propose a verification framework in which we attempt to strike the balance between the expressiveness of theorem proving and the efficiency and automation of state exploration techniques. To this end, we propose to integrate a layer of checking algorithms based on Multiway Decision Graphs (MDG) in the HOL theorem prover. We embedded the MDG underlying logic in HOL and implemented a platform that provides a set of algorithms allowing the user to develop his/her own state-exploration based application inside HOL. While the verification problem is specified in HOL, the proof is derived by tightly combining the MDG based computations and the theorem prover facilities. We have been able to implement different state exploration techniques within HOL such as MDG reachability analysis, equivalence and model checking.
|Divisions:||Concordia University > Faculty of Engineering and Computer Science > Electrical and Computer Engineering|
|Item Type:||Thesis (Masters)|
|Pagination:||xii, 93 leaves ; 29 cm.|
|Degree Name:||Theses (M.A.Sc.)|
|Program:||Electrical and Computer Engineering|
|Thesis Supervisor(s):||Tahar, Sofiene|
|Deposited By:||Concordia University Libraries|
|Deposited On:||27 Aug 2009 17:26|
|Last Modified:||08 Dec 2010 15:25|
Repository Staff Only: item control page