author: Maryam Haji Ghasemi
title: Constant Reduced Decision Diagrams in Meddly
company: Iowa State University (Ames, Iowa, USA)
topics: Algorithms and Data Structures
committee: Gianfranco Ciardo ,
Andrew Miner ,
Jaco van de Pol
started: May 2014
end: August 2014
type: DeSC international research orientation


Binary Decision Diagrams (BDDs) are used in symbolic model checking to represent set of states. Variations of decision diagrams have been introduced as extensions of BDDs. The first extension is removing the constraint of having only binary values, such as Multi-way Decision Diagrams (MDDs ) that can have variables with different domains. It is also possible to extend the range of the encoded function from boolean to integer or real ranges. Both multi-terminal and edge-valued decision diagrams extend this range.

Meddly is a C++ Library that supports both multi-terminal and edge-valued MDDs, and differ- ent reduction rules [2]. It is an ongoing project at Iowa State University (ISU), lead by Prof. Ciardo and Prof. Miner. Currently it supports quasi, fully, and identity-reduction rules. In my internship, I implemented two new reduction rules, constant and CIdentity reduction rules and some basic operations that are useful for model checking.

The concepts that were used during implementation are introduced in Chapter 1. In Chapter 2, the implemented reduction rules and algorithms of some operations are described. This chapter is specially written to guide other researchers to change/add a reduction rule in Meddly. Finally, possible conclusion and future works are presented. 


Additional Resources

  1. The paper