XML-Based Framework for Representation of Decision Diagrams

Abstract

Graph-like structures are often used as a means of organizing data with complex internal structure. In recent decades, decision diagrams, a special class of directed acyclic graphs, have found numerous applications in a wide range of fields, from circuit design and testing to information theory and image processing. A variety of types of decision diagrams have proven to be an efficient method of representation of discrete functions, both in terms of memory size and processing time requirements. Over time a variety of decision diagram types have been introduced to represent different classes of discrete functions and to address different application needs.

At the moment, a plethora of software packages employing decision diagrams in some way is present either in industrial environment, or in academic circles. However, most of these software packages make use of proprietary formats for the internal representation and storage of decision diagrams. This makes data exchange between different software packages difficult. As far as we are aware, no attempt has been made to establish a standard format for the representation of such structures.

Our primary aim is to attempt to amend this situation by proposing a uniform framework for the representation of various classes of decision diagrams. Such a platform needs to satisfy several important criteria. Above all it needs to achieve a high degree of generality, i.e. it should to be able to describe as many as possible of the decision diagram classes introduced so far. It should also be easily extensible in order to accommodate possible new types of decision diagrams that may be introduced in the future. This abstract platform needs to be flexible enough to be transformed into various application specific formats. Finally, one cannot reasonably expect a wide adoption of a new standard which would require radical changes in the present software systems. Thus, this framework needs to be based on a technology that can be easily implemented on most operating systems, and programming environments.

In order to satisfy these criteria, we have chosen to build our framework using XML, an already established data description language created especially for the task of representing complex data structures. In our work we demonstrate that properties of XML make it well suited for the problem of representing decision diagrams. Furthermore, XML is in a wider sense a family of closely related languages dedicated to a particular data manipulation task.

In order to demonstrate the applicability of the proposed framework we exploit the features of XML to convert the abstract representation of decision diagrams into formats suitable for a range of distinct applications, such as hardware register transfer level (RTL) models in VHDL, EDIF based netlists, SVG vector images containing graphical representation of diagrams or branching programs in C++.

The author hopes that the discussion and examples presented in this thesis prove the validity of the chosen approach.