Bochum, Univ., Diss., 2004. / Computerdatei im Fernzugriff.

Freiberg (Sachsen), Techn. Universiẗat, Diss., 2003.

Bochum, University, Diss., 2004.

In der vorliegenden Arbeit werden die Darstellungsmöglichkeiten Boolescher Funktionen durch Neuronale Netze untersucht und eine neue Art von Booleschen Neuronalen Netzen (BNN) entwickelt. Das Basiselement Boolescher Neuronaler Netze ist ein neuartiges Boolesches Neuron (BN), das im Gegensatz zum klassischen Neuron direkt mit Booleschen Signalen operiert und dafür ausschließlich Boolesche Operationen benutzt. Für das Training der BNN wurde ein sequentieller Algorithmus erarbeitet, der eine schnelle Konvergenz garantiert und somit eine kurze Trainingzeit benötigt. Dieser Trainingsalgorithmus bildet die Grundlage eines neuen geschaffenen Verfahrens zur Architektursynthese der BNN. Das entwickelte Training stellt darüber hinaus ein spezielles Dekompositionsverfahren Boolescher Funktionen dar. Neuronale Netze können sowohl in Software als auch in Hardware realisiert werden. Der sehr hohe Aufwand der Hardware-Realisierung üblicher Neuronaler Netze wurde durch die Verwendung von BN und BNN wesentlich vereinfacht. Die Anzahl erforderlicher CLBs (configurable logic blocks) zur Realisierung eines Neurons wurde um 2 Größenordnungen verringert. Ein Boolesches Neuron wird direkt auf eine einzige LUT (lookup table) abgebildet. Für diese sehr kompakte Abbildung der BNN in eine FPGA-Struktur wurde der Trainingsalgorithmus des BNN angepasst. Durch die Spezifikation der BNN mit UML-Modellen und die Anwendung der MDA-Technologie zum Hardware/Software-Codesign konnte der Syntheseaufwand für Hardware-Realisierung von BNN signifikant verringert werden.

In der vorliegenden Arbeit werden die Darstellungsmöglichkeiten Boolescher Funktionen durch Neuronale Netze untersucht und eine neue Art von Booleschen Neuronalen Netzen (BNN) entwickelt. Das Basiselement Boolescher Neuronaler Netze ist ein neuartiges Boolesches Neuron (BN), das im Gegensatz zum klassischen Neuron direkt mit Booleschen Signalen operiert und dafür ausschließlich Boolesche Operationen benutzt. Für das Training der BNN wurde ein sequentieller Algorithmus erarbeitet, der eine schnelle Konvergenz garantiert und somit eine kurze Trainingzeit benötigt. Dieser Trainingsalgorithmus bildet die Grundlage eines neuen geschaffenen Verfahrens zur Architektursynthese der BNN. Das entwickelte Training stellt darüber hinaus ein spezielles Dekompositionsverfahren Boolescher Funktionen dar. Neuronale Netze können sowohl in Software als auch in Hardware realisiert werden. Der sehr hohe Aufwand der Hardware-Realisierung üblicher Neuronaler Netze wurde durch die Verwendung von BN und BNN wesentlich vereinfacht. Die Anzahl erforderlicher CLBs (configurable logic blocks) zur Realisierung eines Neurons wurde um 2 Größenordnungen verringert. Ein Boolesches Neuron wird direkt auf eine einzige LUT (lookup table) abgebildet. Für diese sehr kompakte Abbildung der BNN in eine FPGA-Struktur wurde der Trainingsalgorithmus des BNN angepasst. Durch die Spezifikation der BNN mit UML-Modellen und die Anwendung der MDA-Technologie zum Hardware/Software-Codesign konnte der Syntheseaufwand für Hardware-Realisierung von BNN signifikant verringert werden.

In der vorliegenden Arbeit wird eine Datenstruktur zur Darstellung einer Booleschen Funktion "TVL-Tupel" präsentiert, die im Ergebnis einer Kombination der bekannten Datenstrukturen Entscheidungsgraph und Ternärvektorliste entsteht. Zuerst wird untersucht, wie lokale Phasenlisten sich als Elemente des Tupels eignen. Weiterhin wird die neue Dekompositionsart ("Tupel-Dekomposition") einer Boolesche Funktion in drei bzw. vier Teilfunktionen vorgestellt. Die Besonderheit der Teilfunktionen der Dekomposition besteht in ihrer Orthogonalität zueinander. Der Vorteil der Dekomposition von Funktionen mit einer hohen Anzahl von Konjunktionen besteht im geringeren Speicherplatzbedarf. Des weiteren wurden Algorithmen für Realisierung der Operationen entwickelt, die für eine Handhabung der zerlegten Funktionen erforderlich sind. Der detaillierte Vergleich der Berechnungszeiten für die Operationen erbringt den Nachweis, dass eine Verringerung des Zeitbedarfs als Folge der Zerlegung zu erwarten ist. Weiterhin bietet die Dekomposition einen Ansatz für den Entwurf von Algorithmen, die eine parallele Bearbeitung auf der Grundlage verteilter Rechentechnik zulassen. Die Erkenntnisse der Untersuchungen der Tupel-Dekomposition einschließlich der Verwendung der verteilen Verarbeitung können beispielsweise für die Suche der Variablenmengen der OR-Bi-Decomposition verwendet werden.

Binary Decision Diagrams (BDDs) sind eine Datenstruktur für Boolesche Funktionen, die auch unter dem Namen branching program bekannt ist. In ordered binary decision diagrams (OBDDs) müssen die Tests einer festen Variablenordnung genügen. In free binary decision diagrams (FBDDs) darf jede Variable höchstens einmal getestet werden. Die Effizienz neuer Varianten des BDD-Konzepts wird gewöhnlich anhand spektakulärer (worst-case) Beispiele aufgezeigt. Wir verfolgen einen anderen Ansatz und vergleichen die Darstellungsgrößen für fast alle Booleschen Funktionen. Während I. Wegener bewiesen hat, daß für die `meisten' n die erwartete OBDD-Größe einer zufälligen Booleschen Funktion von n Variablen gleich der worst-case Größe bis auf Terme kleinerer Ordnung ist, zeigen wir daß dies nicht der Fall ist für n innerhalb von Intervallen konstanter Länge um die Werte n = 2h + h. Ferner gibt es Bereiche von n, in denen minimale FBDDs fast immer um mindestens einen konstanten Faktor kleiner sind als minimale OBDDs. Unsere Hauptsätze ha ben doppelt exponentielle Wahrschein- lichkeitsschranken (in n). Außerdem untersuchen wir die Entwicklung zufälliger OBDDs und ihrer worst-case Größe und decken dabei ein oszillierendes Verhalten auf, das erklärt, warum gewisse Aussagen im allgemeinen nicht verstärkt werden können. / Binary Decision Diagrams (BDDs) are a data structure for Boolean functions which are also known as branching programs. In ordered binary decision diagrams (OBDDs), the tests have to obey a fixed variable ordering. In free binary decision diagrams (FBDDs), each variable can be tested at most once. The efficiency of new variants of the BDD concept is usually demonstrated with spectacular (worst-case) examples. We pursue another approach and compare the representation sizes of almost all Boolean functions. Whereas I. Wegener proved that for `most' values of n the expected OBDD size of a random Boolean function of n variables is equal to the worst-case size up to terms of lower order, we show that this is not the case for n within intervals of constant length around the values n = 2h + h. Furthermore, ranges of n exist for which minimal FBDDs are almost always at least a constant factor smaller than minimal OBDDs. Our main theorems have doubly exponentially small probability bounds (in n). We also investigate the evolution of random OBDDs and their worst-case size, revealing an oscillating behaviour that explains why certain results cannot be improved in general.

In der vorliegenden Arbeit wird eine Datenstruktur zur Darstellung einer Booleschen Funktion "TVL-Tupel" präsentiert, die im Ergebnis einer Kombination der bekannten Datenstrukturen Entscheidungsgraph und Ternärvektorliste entsteht. Zuerst wird untersucht, wie lokale Phasenlisten sich als Elemente des Tupels eignen. Weiterhin wird die neue Dekompositionsart ("Tupel-Dekomposition") einer Boolesche Funktion in drei bzw. vier Teilfunktionen vorgestellt. Die Besonderheit der Teilfunktionen der Dekomposition besteht in ihrer Orthogonalität zueinander. Der Vorteil der Dekomposition von Funktionen mit einer hohen Anzahl von Konjunktionen besteht im geringeren Speicherplatzbedarf. Des weiteren wurden Algorithmen für Realisierung der Operationen entwickelt, die für eine Handhabung der zerlegten Funktionen erforderlich sind. Der detaillierte Vergleich der Berechnungszeiten für die Operationen erbringt den Nachweis, dass eine Verringerung des Zeitbedarfs als Folge der Zerlegung zu erwarten ist. Weiterhin bietet die Dekomposition einen Ansatz für den Entwurf von Algorithmen, die eine parallele Bearbeitung auf der Grundlage verteilter Rechentechnik zulassen. Die Erkenntnisse der Untersuchungen der Tupel-Dekomposition einschließlich der Verwendung der verteilen Verarbeitung können beispielsweise für die Suche der Variablenmengen der OR-Bi-Decomposition verwendet werden.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.