Computer Intelligence and Learning PhD student day (collocated with ECML PKDD 2008) edition:3 location:Antwerp date:15-19 September 2008
We developed a tool, named simpleCUDD, to unify and simplify the use of Binary Decision Diagrams (BDDs).
The Colorado University Decision Diagrams library (CUDD) is an efficient library for BDDs. However it is difficult to use CUDD from external applications.
To overcome this difficulty we developed a unified and simple interface (simpleCUDD) for applications using BDDs.
SimpleCUDD makes the use of CUDD much easier while it retains all of the efficiency and the power of CUDD. It can be seen/used as an equivalent of the C++ interface of CUDD, but simpleCUDD was developed completely in C to keep it fast and as portable as possible.
Both the generation of the BDD and the traversal of BDDs have been simplified. The user does not need any longer to write code to specify the underlying function of the BDD, instead the user describes the function more naturally as a script. Traversing the resulting BDD has been simplified with the use of node history and dedicated functions. Furthermore, simpleCUDD adds extra functionality like BDD description files, named variables, traversed node history, node value assignment and finally an efficient saving method for the generated BDDs.
The new saving algorithm has been compared with the existing methods (DDDMP) for result validity and performance. SimpleCUDD performs equally well in most cases and for some functions, especially more complex ones, better than DDDMP.
SimpleCUDD has been used successfully in applications like: ProbLog (Luc De Raedt et al.) and LeProbLog (Bernd Gutmann et al.).
Future work consists in improving further the BDD saving algorithm, and develop a Prolog library for using simpleCUDD directly from Prolog.