Abgeschlossene Promotionen

Ch. Lang: Bi-Decomposition of Function Sets using Multi-Valued Logic

This dissertation presents a theory for the bi-decomposition of functions in multi-valued logic (MVL). MVL functions are applied in logic design of multi-valued circuits and machine learning applications. Bi-decomposition is a method to decompose a function into two decomposition functions that are connected by a two-input operator called gate. Each of the decomposition functions depends on fewer variables than the original function. Recursive bi-decomposition represents a function as a structure of interconnected gates. For logic synthesis, the type of the gate can be chosen so that it has an effcient hardware representation. For machine learning, gates are selected to represent simple and understandable classification rules.

To describe the MVL bi-decomposition theory, the notion of incompletely specified functions is generalized to function sets. Particular classes of function sets, such as function intervals, relations and lattices, are identified. Properties of bi-decompositions are analyzed by means of these function sets.

Algorithms are presented for non-disjoint bi-decomposition, where the decomposition functions may share variables with each other. Bi-decomposition is discussed for monotone operators, which are of special interest in machine learning. They lead to rules that can easily be understood by humans. For the special case of min- and max-decomposition, the theory of bi-decomposition for Boolean functions using the Boolean differential calculus is extended, leading to particular efficient algorithms. The thesis also introduces new classes of operators, such as simple operators, and presents the corresponding decomposition algorithms.

The decomposition algorithms are implemented in a decomposition system called YADE. MVL test functions from machine learning and logic synthesis applications are decomposed. The results are compared to other decomposers. It is verfied that YADE finds decompositions of superior quality by bi-decomposition of MVL function sets. The applicability of the proposed approach to machine learning is demonstrated by the decomposition of real-world data mining example into an easily interpretable set of classification rules.


 

K. Hesse: Ein Beitrag zur Lösung hochdimensionaler Boolescher Probleme mit parallelen Algorithmen

Die vorliegende Arbeit befasst sich mit der Parallelisierung von Algorithmen für die Boolesche Mengenalgebra bzw. den Booleschen Differentialkalkül. Das Ziel besteht in der Entwicklung einer universellen Bibliothek zur Behandlung hochdimensionaler Boolescher Probleme, wie sie auf vielen Gebieten, vor allem jedoch im Schaltkreisentwurf auftreten. Aufbauend auf dem adäquat referierten internationalen Stand dieses Forschungsfeldes, werden Prämissen für die Entwicklung einer solchen Bibliothek abgeleitet und explizit aufgeführt.

Die entwickelten Algorithmen werden in metasprachlicher Notation dargestellt, um eine hohe Portabilität zu erreichen. Die Arbeit richtet außerdem besonderes Augenmerk auf eine gute Skalierbarkeit der parallelen Algorithmen. Daher wurden als Zielsystem für die Entwicklung parallele Rechner mit verteiltem Speicher (Distributed Memory Systeme) ausgewählt.

Der Hauptdatentyp der vorgestellten Bibliothek ist die orthogonale Ternärvektorliste. Die entworfenen Algorithmen werden mathematisch exakt begründet und ihre Darstellung durch ausführliche Komplexitätsbetrachtungen ergänzt. Es erfolgte eine prototypische Implementation der Algorithmen auf einem Transputersystem, deren Ergebnisse einer kritischen Wertung unterzogen werden.