Multiway Decision Graphs Reduction Approach based on the HOL Theorem Prover

Abstract

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.

Contributors

Sa’ed Abed

Otmane Ait Mohamed

Ghiath Al Sammane

Conference

Publication date: July 2008

Publication date (Print): July 2008

Pages: 1-10

Affiliations

Department of Electrical and Computer Engineering

Concordia University, Montreal, Canada

Article

DOI: 10.14236/ewic/VECOS2008.2

Copyright statement: © Sa’ed Abed et al. Published by BCS Learning and Development Ltd. Second International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2008)

License:

This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Conference name: Second International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2008)

Conference acronym: VECoS

Conference number:

Conference location: Leeds, UK

Conference date: 2 - 3 July 2008

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: Verification and Evaluation of Computer and Communication Systems

Product

Product Information: 1477-9358BCS Learning & Development

Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/VECOS2008.2

Self URI (journal page): https://ewic.bcs.org/

Categories

Series title: Electronic Workshops in Computing