A Java library for Zero-Suppressed Decision Diagrams

Abstract

On the one hand, decision diagrams are a common means to represent Boolean functions. Since they were first proposed in the 80s, they became more and more popular. They are widely used in circuit optimization and verification and are useful when dealing with combinatorial problems. Zero-Suppressed Decision Diagram (ZDD)s are one type of those diagrams. On the other hand, Java is presently one of the most popular programming languages. Much research was done on each of these two subjects, ZDDs and Java, separately, but not on a combination of both. There is no appropriate library for Java implementing ZDDs. In the course of this thesis such a library was developed and implemented. The thesis describes the basic functionality of decision diagrams and lists particularities regarding the realization of them. Finally, the results of benchmarks for the library in general and the optimizations in particular are presented and discussed.

Einerseits sind Entscheidungsdiagramme ein weit verbreitetes Mittel, um Boolsche Funktionen darzustellen. Seit sie in den 80er-Jahren erstmals vorgeschlagen wurden, wurden sie immer populärer. Sie werden häufig in Schaltkreisoptimierung und -verifikation eingesetzt und sind nützlich bei kombinatorischen Problemen. ZDDs sind eine Art dieser Diagramme. Andererseits ist Java heutzutage eine der beliebtesten Programmiersprachen. Viele Arbeiten wurden jeweils über ZDDs und Java durchgeführt, aber nicht über der Vereinigung dieser beiden Forschungsgebiete.Es gibt keine angemessene Bibliothek für Java, die ZDDs implementiert. Eine solche Bibliothek wurde im Verlauf dieser Arbeit entwickelt und implementiert. Die Arbeit beschreibt die grundlegenden Funktionen von Entscheidungsdiagrammen und nennt Besonderheiten diesbezüglich. Zum Schluss werden die Ergebnisse der Benchmarks für die Bibliothek im Allgemeinen und die Optimierungen im Besonderen präsentiert und diskutiert.