Unter dem Evolutionsprozeß eines Objekts, das aus einer gegebenen Klasse zufällig ausgewählt wird, versteht man das folgende Gedankenexperiment. Zu einem geeigneten Parameter der Objekte der Klasse betrachtet man die Teilklasse derjenigen Objekte, bei denen dieser Parameter einen bestimmten Wert x annimmt. Dadurch stellen sich die folgenden Fragen: Wie sieht ein typisches Objekt dieser Teilklasse aus? Wieviele Objekte gibt es in der Teilklasse? Und: Wie verändern sich die Antworten auf die ersten beiden Fragen, wenn sich x verändert? Die vorliegende Dissertation behandelt Phasenübergänge im Evolutionsprozeß teilweiser Ordnungen und bestimmt die Anzahl teilweiser Ordnungen mit einer gegebenen Anzahl vergleichbarer Paare. Wir bezeichnen durch Pn,d die Klasse aller teilweisen Ordnungen mit n Punkten und dn2 vergleichbaren Paaren. 1978 bestimmte Dhar |Pn,d| im Intervall 1/8 < d < 3/16 und zeigte, daß hier eine typische Ordnung aus drei "Ebenen" besteht. 1979 bestimmten Kleitman und Rothschild |Pn,d| im Intervall 0 < d < 1/8 und zeigten, daß hier eine typische Ordnung aus zwei Ebenen besteht, also bipartit ist. Das Hauptergebnis der Dissertation ist es, ein vollständiges Bild des Evolutionsprozesses zu geben. Wir bestimmen |Pn,d| im gesamten Intervall 0 < d < 1/2 und zeigen, daß es unendlich viele Phasenübergänge gibt. Abschließend beschreiben wir, wie sich die Struktur einer typischen Ordnung während dieser Phasen verändert. / The evolution process of a random structure from a certain class denotes the following "experiment". Choose a parameter of the objects in the class under consideration and consider only the subclass of those objects where the parameter is equal to a fixed value x. Then the following questions arise quite naturally: What does a typical object from this subclass look like? How many objects are there in this subclass? And how do the answers to the first two questions change when x changes? This thesis investigates the phase transitions in the evolution of partially ordered sets and determines the number of partially ordered sets with a given number of comparable pairs. Denote by Pn,d the class of all n-point posets with dn2 comparable pairs. In 1978, Dhar determined |Pn,d| in the range 1/8 < d < 3/16 and showed that here a typical poset consists of three layers. In 1979, Kleitman and Rothschild determined |Pn,d| in the range 0 < d < 1/8 and showed that here a typical poset consists of two layers, i.e. it is bipartite. The main result of this thesis is to complete the picture by describing the whole evolution process of Pn,d in the range 0 < d < 1/2. We determine |Pn,d| for any d and show that there exist an infinite number of phase transitions. Finally we describe how the structure of a typical partially ordered set changes during these phases.

Das Lernen aus strukturierten Eingabe- und Ausgabebeispielen ist die Grundlage für die automatisierte Verarbeitung natürlich auftretender Problemstellungen und eine Herausforderung für das Maschinelle Lernen. Die Einordnung von Objekten in eine Klassentaxonomie, die Eigennamenerkennung und das Parsen natürlicher Sprache sind mögliche Anwendungen. Klassische Verfahren scheitern an der komplexen Natur der Daten, da sie die multiplen Abhängigkeiten und Strukturen nicht erfassen können. Zudem ist die Erhebung von klassifizierten Beispielen in strukturierten Anwendungsgebieten aufwändig und ressourcenintensiv, während unklassifizierte Beispiele günstig und frei verfügbar sind. Diese Arbeit thematisiert halbüberwachte, diskriminative Vorhersagemodelle für strukturierte Daten. Ausgehend von klassischen halbüberwachten Verfahren werden die zugrundeliegenden analytischen Techniken und Algorithmen auf das Lernen mit strukturierten Variablen übertragen. Die untersuchten Verfahren basieren auf unterschiedlichen Prinzipien und Annahmen, wie zum Beispiel der Konsensmaximierung mehrerer Hypothesen im Lernen aus mehreren Sichten, oder der räumlichen Struktur der Daten im transduktiven Lernen. Desweiteren wird in einer Fallstudie zur Email-Batcherkennung die räumliche Struktur der Daten ausgenutzt und eine Lösung präsentiert, die der sequenziellen Natur der Daten gerecht wird. Aus den theoretischen Überlegungen werden halbüberwachte, strukturierte Vorhersagemodelle und effiziente Optmierungsstrategien abgeleitet. Die empirische Evaluierung umfasst Klassifikationsprobleme, Eigennamenerkennung und das Parsen natürlicher Sprache. Es zeigt sich, dass die halbüberwachten Methoden in vielen Anwendungen zu signifikant kleineren Fehlerraten führen als vollständig überwachte Baselineverfahren. / Learning mappings between arbitrary structured input and output variables is a fundamental problem in machine learning. It covers many natural learning tasks and challenges the standard model of learning a mapping from independently drawn instances to a small set of labels. Potential applications include classification with a class taxonomy, named entity recognition, and natural language parsing. In these structured domains, labeled training instances are generally expensive to obtain while unlabeled inputs are readily available and inexpensive. This thesis deals with semi-supervised learning of discriminative models for structured output variables. The analytical techniques and algorithms of classical semi-supervised learning are lifted to the structured setting. Several approaches based on different assumptions of the data are presented. Co-learning, for instance, maximizes the agreement among multiple hypotheses while transductive approaches rely on an implicit cluster assumption. Furthermore, in the framework of this dissertation, a case study on email batch detection in message streams is presented. The involved tasks exhibit an inherent cluster structure and the presented solution exploits the streaming nature of the data. The different approaches are developed into semi-supervised structured prediction models and efficient optimization strategies thereof are presented. The novel algorithms generalize state-of-the-art approaches in structural learning such as structural support vector machines. Empirical results show that the semi-supervised algorithms lead to significantly lower error rates than their fully supervised counterparts in many application areas, including multi-class classification, named entity recognition, and natural language parsing.

Edsger W. Dijkstra prägte im Jahr 1974 den Begriff Selbststabilisierung (self-stabilization) in der Informatik. Ein System ist selbststabilisierend, wenn es von jedem denkbaren Zustand aus nach einer endlichen Anzahl von Aktionen ein stabiles Verhalten erreicht. Im Mittelpunkt dieser Arbeit steht der Entwurf selbststabilisierender Algorithmen. Wir stellen eine Petrinetz-basierte Methode zum Entwurf selbststabilisierender Algorithmen vor. Wir validieren unsere Methode an mehreren Fallstudien: Ausgehend von algorithmischen Ideen existierender Algorithmen beschreiben wir jeweils die die schrittweise Entwicklung eines neuen Algorithmus. Dazu gehört ein neuer randomisierter selbststabilisierender Algorithmus zur Leader Election in einem Ring von Prozessoren. Dieser Algorithmus ist abgeleitet aus einem publizierten Algorithmus, von dem wir hier erstmals zeigen, daß er fehlerhaft arbeitet. Wir weisen die Speicherminimalität unseres Algorithmus nach. Ein weiteres Ergebnis ist der erste Algorithmus, der ohne Time-Out-Aktionen selbststabilisierenden Tokenaustausch in asynchronen Systemen realisiert. Petrinetze bilden einen einheitlichen formalen Rahmen für die Modellierung und Verifikation dieser Algorithmen. / In 1974, Edsger W. Dijkstra suggested the notion of self-stabilization. A system is self-stabilizing if regardless of the initial state it eventually reaches a stable behaviour. This thesis focuses on the design of self-stabilizing algorithms. We introduce a new Petri net based method for the design of self-stabilizing algorithms. We validate our method on several case studies. In each of the case studies, our stepwise design starts from an algorithmic idea and leads to a new self-stabilizing algorithm. One of these algorithms is a new randomized self-stabilizing algorithm for leader election in a ring of processors. This algorithm is derived from a published algorithm which we show to be incorrect. We prove that our algorithm is space-minimal. A further result is the first algorithm for token-passing in a asynchronous environment which works without time-out actions. Petri nets form a unique framework for modelling and verification of these algorithms.

Proteininteraktionen sind entscheidend für zelluläre Funktion. Interaktionen reflektieren direkte funktionale Beziehungen zwischen Proteinen. Veränderungen in spezifischen Interaktionsmustern tragen zur Entstehung von Krankheiten bei. In dieser Arbeit werden funktionale und pathologische Aspekte von Proteininteraktionen analysiert, um Funktionen für bisher nicht charakterisierte Proteine vorherzusagen und Proteine mit Krankheitsphänotypen zu assoziieren. Verschiedene Methoden wurden in den letzten Jahren entwickelt, die die funktionalen Eigenschaften von Proteinen untersuchen. Dennoch bleibt ein wesentlicher Teil der Proteine, insbesondere menschliche, uncharakterisiert. Wir haben eine Methode zur Vorhersage von Proteinfunktionen entwickelt, die auf Proteininteraktionsnetzwerken verschiedener Spezies beruht. Dieser Ansatz analysiert funktionale Module, die über evolutionär konservierte Prozesse definiert werden. In diesen Modulen werden Proteinfunktionen gemeinsam über Orthologiebeziehungen und Interaktionspartner vorhergesagt. Die Integration verschiedener funktionaler Ähnlichkeiten ermöglicht die Vorhersage neuer Proteinfunktionen mit hoher Genauigkeit und Abdeckung. Die Aufklärung von Krankheitsmechanismen ist wichtig, um ihre Entstehung zu verstehen und diagnostische und therapeutische Ansätze zu entwickeln. Wir stellen einen Ansatz für die Identifizierung krankheitsrelevanter Genprodukte vor, der auf der Kombination von Proteininteraktionen, Proteinfunktionen und Netzwerkzentralitätsanalyse basiert. Gegeben einer Krankheit, werden krankheitsspezifische Netzwerke durch die Integration von direkt und indirekt interagierender Genprodukte und funktionalen Informationen generiert. Proteine in diesen Netzwerken werden anhand ihrer Zentralität sortiert. Das Einbeziehen indirekter Interaktionen verbessert die Identifizierung von Krankheitsgenen deutlich. Die Verwendung von vorhergesagten Proteinfunktionen verbessert das Ranking von krankheitsrelevanten Proteinen. / Protein interactions are essential to many aspects of cellular function. On the one hand, they reflect direct functional relationships. On the other hand, alterations in protein interactions perturb natural cellular processes and contribute to diseases. In this thesis we analyze both the functional and the pathological aspect of protein interactions to infer novel protein function for uncharacterized proteins and to associate yet uncharacterized proteins with disease phenotypes, respectively. Different experimental and computational approaches have been developed in the past to investigate the basic characteristics of proteins systematically. Yet, a substantial fraction of proteins remains uncharacterized, particularly in human. We present a novel approach to predict protein function from protein interaction networks of multiple species. The key to our method is to study proteins within modules defined by evolutionary conserved processes, combining comparative cross-species genomics with functional linkage in interaction networks. We show that integrating different evidence of functional similarity allows to infer novel functions with high precision and a very good coverage. Elucidating the pathological mechanisms is important for understanding the onset of diseases and for developing diagnostic and therapeutic approaches. We introduce a network-based framework for identifying disease-related gene products by combining protein interaction data and protein function with network centrality analysis. Given a disease, we compile a disease-specific network by integrating directly and indirectly linked gene products using protein interaction and functional information. Proteins in this network are ranked based on their network centrality. We demonstrate that using indirect interactions significantly improves disease gene identification. Predicted functions, in turn, enhance the ranking of disease-relevant proteins.

Domänenspezifische Sprachen (DSLs) sind Software-Sprachen, die speziell für bestimmte Anwendungsdomänen entwickelt wurden. Mithilfe von DSLs können Domänenexperten ihr Domänenwissen auf einem hohen Abstraktionsniveau beschreiben. Wie andere Software-Sprachen auch, benötigen DSLs Sprachwerkzeuge, die Assistenz bei der Erstellung und Verarbeitung von domänenspezifischen Modellen bieten. Eine domänenspezifische Werkbank (DSW) ist ein Software-Werkzeug, welches mehrere solcher Sprachwerkzeuge für eine DSL miteinander integriert. Existierende Werkzeuge, die es erlauben eine DSW aufgrund der Beschreibung einer DSL automatisch generieren zu lassen, unterstützen jedoch nicht die Beschreibung und Generierung von editierbaren Sichten. Eine Sicht ist ein Teil einer DSW, der nur einen bestimmten Aspekt eines Modells darstellt. Diese Dissertation stellt spezielle Modelltransformationssprachen (MTLs) vor, mit denen die Synchronisation von Sichten in einer generierten DSW beschrieben werden kann. Dadurch können DSWs mit editierbaren Sichten mittels existierender Werkzeuge zur Generierung von Sprachwerkzeugen erstellt werden. Dafür wird eine DSW für die Nanophysik-Domäne sowie eine Taxonomie von Synchronisationstypen vorgestellt, welche es erlaubt genau zu bestimmen, welche Art von Modelltransformationen für die Synchronisation von Sichten in dieser Werkbank benötigt werden. Entsprechend dieser Anforderungen werden zwei MTLs entwickelt. Insbesondere wird eine bidirektionale MTL entwickelt. Mit solch einer Sprache kann man eine Relation, welche definiert ob zwei Modelle synchron sind, so beschreiben, dass die entsprechende Synchronisationslogik automatisch abgeleitet werden kann. Die gezeigten MTLs werden als interne DSLs - das heißt eingebettet als ausdrucksstarke Bibliotheken - in der Programmiersprache Scala implementiert. Auf diese Weise kann Scalas Typprüfung genutzt werden, um Transformationen und deren Komposition statisch zu verifizieren. / Domain-specific languages (DSLs) are software languages which are tailored to a specific application domain. DSLs enable domain experts to create domain-specific models, that is, high-level descriptions of domain knowledge. As any other software languages, DSLs rely on language tools which provide assistance for processing and managing domain-specific models. A domain-specific workbench is an integrated set of such tools for a DSL. A recently proposed approach is to automatically generate a domain-specific workbench for a DSL from a description of that DSL. However, existing tools which apply this approach do not support to describe and generate editable domain-specific views. A view is a part of domain-specific workbench that presents only one aspect of a model, for example, its hierarchical structure. This dissertation presents special model transformation languages which support the description of view synchronization in a generated domain-specific workbench. This allows a multi-view domain-specific workbench to be created with existing tools for language tool generation. We present a generated domain-specific workbench for the nanophysics domain and present a taxonomy of synchronization types. This allows us to precisely define what model transformations are required for view synchronization in that workbench. According to these requirements, we develop two transformation languages by adapting existing ones. In particular, we develop a bidirectional transformation language. With such a language one can describe a relation which defines whether two models are in sync and let the synchronization logic be inferred automatically. We implement model transformation languages as internal DSLs - that is, embedded as expressive libraries - in the Scala programming language and use Scala''s type checking for static verification of transformations and their composition.

Durch Kreuzkorrelation von ECoG- und EEG-Signalen hoher Bandbreite (10 - 400 Hz) mit dem Muster eines Amplituden - Zeit - Templates von 10 ms Dauer können Subpotentiale (SP) selektiert werden, die dem sogenannten ?local field potential? ähnlich sind.Diese Ähnlichkeit ergibt sich i. durch den Vergleich mit dem ermittelten Amplituden - Zeit - Template des SP. ii. durch den Vergleich mit der Lage der Quellstrukturen zur ableitenden Elektrode. Die SP - Modulanalyse liefert Potentialverteilung für jede untersuchte Elektrode. Diese ist stets in ein Nahfeld und Fernfelder organisiert, wobei die Polarität des Nahfeld der Polarität des Trigger- SP entspricht und das Fernfeld von entgegengesetzter Polarität ist. Diese Quellstrukturen sind um so kleiner, je geringer der Elektrodenabstand ist. iii. aus der Kohärenz von SP, die im Ableitfeld auftreten. Dafür wurde die SP- Zweikanalkopplungsanalyse entwickelt.Die einzelnen Schritte dieser SP - Methode, die sich aus der SP - event-, SP - Modul- und SP - Zweikanalkopplungsanalyse zusammensetzt, werden beschrieben und an einem Beispiel einer 30 kanaligen subduralen interiktalen ECoG - Ableitung eines Patienten mit fokaler Epilepsie unter drei verschiedenen Bedingungen (normales ECoG, ECoG mit spikes bzw. ECoG mit slow waves) sowie am Beispiel einer 30 kanaligen EEG-Ableitung eines Probanden unter drei verschiedenen kognitiven Anforderungen (relaxierte Wachheit, Kopfrechnen, beim Anhören eines Hörspiels) vergleichend demonstriert. Beide Beispiele sind repräsentativ für zwei größere Untersuchungsreihen. / We obtained subpotentials (SP), similar to so called ?local field potentials? by application of cross - correlation on ECoG- and EEG- Signals with large band width (10 - 400 Hz) with the pattern of an amplitude-time-template with a duration of 10ms. This similarity is given by i. the comparison with obtained amplitude-time-template of the SP ii. the comparison with the position of source- structures to the deriving electrode. The potential distribution is given by the SP - moduleanalysis for each investigated electrode. This SP - module - analysis is always organised in a near- and in a far-field. The polarity of the near-field corresponds to the trigger-SP and the far-field to the opposite. The smaller the source-structure, the lower the distance of the electrodes iii.the coherence of SP in the deriving array The SP - method, consisting of SP - event, SP - module and SP ?two-channel-coupling -analysis? is described. The comparison between an example of an 30 channel subdural interictal derived ECoG of a patient, who was suffering from focal epilepsy, under three conditions (normal ECoG, ECoG with spikes and ECoG with slow-waves) and one of an 30 channel derived EEG of a candidate under three different cognitive demands (relaxed vigilance, doing mental arithmetic, listening to a radio serial) is demonstrated an discussed. Both examples are representatives for two extensive serials.

Globally Asynchronous Locally Synchronous (GALS) Design ist eine Lösung zur Skalierbarkeit und Modularität für die SoC-Integration. Heutzutage ist GALS-Design weit in der Industrie angewendet. Die meisten GALS-Systeme basieren auf Dual-Clock-FIFOs für die Kommunikation Zwischen Taktdomänen. Um Leistungsverluste aufgrund der Synchronisationslatenzzeit zu vermindern, müssen die On-Chip-FIFOs ausreichend groß sein. Dies führt jedoch oft zu erheblichen Kosten-Hardware. Effiziente GALS- Lösungen sind daher vonnöten. Diese Arbeit berichtet unsere neuesten Fortschritte in GALS Design, das auf der Pausierenden Taktung basiert. Kritische Designthemen in Bezug auf Synchronisation-szuverlässigkeit bzw. Kommunikationsfähigkeit sind systematisch und analytisch un-tersucht. Ein lose gekoppeltes GALS Data-Link-Design wird vorgeschlagen. Es unter-stützt metastabilitätsfreie Synchronisation für Sub-Takt-Baum Verzögerungen. Außer-dem unterstützt es kontinuierliche Datenübertragung für High-Throughput-Kommuni-kation. Die Rosten hinsichtlich Energie verbrauch und Chipfläche sind marginal. GALS Design ist eingesetzt, um digitales On-Chip Umschaltrauschen zu verringern. Plesiochron Taktung mit balanciertem Leistungsverbrauch zwischen GALS Blöcken wird insbesondere untersucht. Für M Taktbereiche wird eine Reduzierung um 20lgM dB für die spektralen Spitzen des Versorgungsstroms bei der Takt-Grundfrequenz theoretisch hergcleitet. Im Vergleich zu den bestehenden synchronen Lösungen, geben diese Methode eine Alternative, um das digitale schaltrauschen effektiv zu senken. Schließlich wurde die entwickelte GALS Design Methodik schon bei reale Chip-Implementierungen angewendet. Zwei komplizierte industriell relevante Test-Chips, Lighthouse und Moonrake, wurden entworfen und mit State-Of-The-Art-Technologien hergestellt. Die experimentellen Ergebnisse bzw. / Globally asynchronous locally synchronous (GALS) design presents a solution of scalability and modularity to SoC integration. Today, it has been widely applied in the industry. Most of the GALS systems are based on dual-clock FIFOs for clock domain crossing. To avoid performance loss due to synchronization latency, the on-chip FIFOs need to be sufficiently large. This, however, often leads to considerable hardware costs. Efficient design solutions of GALS are therefore in great demand. This thesis reports our latest progress in GALS design bases on pausible clocking. Critical design issues on synchronization reliability and communication performance are studied systematically and analytically. A loosely-coupled GALS data-link design is proposed. It supports metastability-free synchronization for sub-cycle clock-tree delay, and accommodates continuous data transfer for high-throughput communication. Only marginal costs of power and silicon area are required. GALS design has been employed to cope with the on-chip digital switching noise in our work. Plesiochronous clocking with power-consumption balance between GALS blocks is in particular explored. Given M clock domains, a reduction of 20lgM dB on the spectral peaks of supply current at the fundamental clock frequency is theoretically derived. In comparison with the existing synchronous design solutions, it thus presents an alternative to effective attenuation of digital switching noise. The developed GALS design methodology has been applied to chip implementation. Two complicated industry-relevant test chips, named Lighthouse and Moonrake, were designed and fabricated using state-of-the-art technologies. The experimental results as well as the on-chip measurements are reported here in detail. We expect that, our work will contribute to the practical applications of GALS design based on pausible clocking in the industry.

Motiviert durch strukturelle Eigenschaften molekularer Ähnlichkeitsnetzwerke werden die Evolution der größten Komponente eines Netzwerkes in zwei verschiedenen stochastischen Modellen, zufälligen Hypergraphen und zufälligen Schnittgraphen, untersucht. Zuerst wird bewiesen, dass die Anzahl der Knoten in der größten Komponente d-uniformer Hypergraphen einer Normalverteilung folgt. Der Beweis nutzt dabei ausschließlich probabilistische Argumente und keine enumerative Kombinatorik. Diesem grundlegenden Resultat folgen weitere Grenzwertsätze für die gemeinsame Verteilung von Knoten- und Kantenzahl sowie Sätze zur Zusammenhangswahrscheinlichkeit zufälliger Hypergraphen und zur asymptotischen Anzahl zusammenhängender Hypergraphen. Da das Hypergraphenmodell einige Eigenschaften der Realweltdaten nur unzureichend abbildet, wird anschließend die Evolution der größten Komponente in zufälligen Schnittgraphen, die Clustereigenschaften realer Netzwerke widerspiegeln, untersucht. Es wird gezeigt, dass zufällige Schnittgraphen sich von zufälligen (Hyper-)Graphen dadurch unterscheiden, dass (bei einer durchschnittlichen Nachbaranzahl von mehr als eins) weder die größte Komponente linear noch die zweitgrößte Komponente logarithmisch groß in Abhängigkeit von der Knotenzahl ist. Weiterhin wird ein Polynomialzeitalgorithmus zur Überdeckung der Kanten eines Graphen mit möglichst wenigen Cliquen (vollständigen Graphen) beschrieben und seine asymptotische Optimalität im Modell der zufälligen Schnittgraphen bewiesen. Anschließend wird die Entwicklung der chromatischen Zahl untersucht und gezeigt, dass zufällige Schnittgraphen mit hoher Wahrscheinlichkeit mittels verschiedener Greedystrategien optimal gefärbt werden können. Letztendlich zeigen Experimente auf realen Netzen eine Übereinstimmung mit den theoretischen Vorhersagen und legen eine gegenseitige Zertifizierung der Optimalität von Cliquen- und Färbungszahl durch Heuristiken nahe. / Motivated by structural properties of molecular similarity networks we study the behaviour of the component evolution in two different stochastic network models, that is random hypergraphs and random intersection graphs. We prove gaussian distribution for the number of vertices in the giant component of a random d-uniform hypergraph. We provide a proof using only probabilistic arguments, avoiding enumerative methods completely. This fundamental result is followed by further limit theorems concerning joint distributions of vertices and edges as well as the connectivity probability of random hypergraphs and the number of connected hypergraphs. Due to deficiencies of the hypergraph model in reflecting properties of the real--world data, we switch the model and study the evolution of the order of the largest component in the random intersection graph model which reflects some clustering properties of real--world networks. We show that for appropriate choice of the parameters random intersection graphs differ from random (hyper-)graphs in that neither the so-called giant component, appearing when the average number of neighbours of a vertex gets larger than one, has linear order nor is the second largest of logarithmic order in the number of vertices. Furthermore we describe a polynomial time algorithm for covering graphs with cliques, prove its asymptotic optimality in a random intersection graph model and study the evolution of the chromatic number in the model showing that, in a certain range of parameters, these random graphs can be coloured optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.

Vor allem bei der Betrachtung großer und komplexer Szenarien ist eine Kombination der Vorteile der sequentiellen und parallelen Simulationswelten wünschenswert. Derartige Szenarien lassen sich meist nur bei einer adäquaten, strukturäquivalenten Modellierung, wie in der sequentiellen Simulationswelt üblich, beherrschen. Es sind aber auch gleichzeitig genau diese Simulationsszenarien, die auch am ehesten nach einer Beschleunigung der Simulationsausführung, z.B. durch eine Parallelisierung, verlangen. Die vorliegende Arbeit beschreibt die Konzeption und Implementation einer optimistisch-parallelen Simulationsbibliothek in Java. Diese vereint die Vorzüge optimistisch-paralleler Simulation (automatische Ausnutzung modellinhärenter Parallelität zur Simulationsbeschleunigung) mit der des prozessorientierten Paradigmas (modellabhängig strukturäquivalente und intuitive Modellbeschreibungen). Eine Implementation des prozessorientierten Paradigmas in einer parallelen Simulation ist allerdings nicht unproblematisch. Dies gilt vor allem im Spezialfall der optimistisch-parallelen Simulation, die sich dadurch auszeichnet, dass Simulationsmodelle während eines Simulationslaufes in ungültige Zustände geraten können, was jeweils durch eine Rückkehr des Simulationsmodells in einen früheren, korrekten Zustand korrigiert wird. Ein weiteres Entwicklungsziel besteht darin, im Gegensatz zu den meisten existierenden PDES-Implementationen die interne Arbeitsweise des optimistisch-parallelen Simulationskerns so gut wie möglich zu verbergen. Stattdessen gleichen die vom Simulationskern angebotenen Schnittstellen weitestgehend denen von sequentiellen Simulationskernen. Dadurch wird die Erstellung eines passenden Simulationsmodells im Vergleich zu anderen parallelen Simulationsimplementationen deutlich erleichtert. Auch der Mehraufwand gegenüber der Erstellung von Simulationsmodellen für rein sequentielle Simulationskerne ist relativ gering. / A combination of the advantages of the sequential, as well as the parallel simulation approach is desirable, especially in the case of large and complex simulation scenarios. These are only manageable if a corresponding structurally equivalent simulation model is employed. Also, the very same models will profit most from a speed-up by parallelization. Unfortunately, the implementation of a process-oriented view in a parallel fashion is not a trivial task. Parallel simulation implementations generally suffer from additional computational cost that can offset the parallel speed-up and even lead to a diminished parallel performance, which is even more likely to happen when using process-oriented simulation models. This is especially the case in optimistic-parallel simulations. These are characterized by the ability of the model to get into invalid states which is costly being corrected at runtime by returning the model to valid former states preliminarily saved. The aim of this thesis is the design and implementation of a simulation library in Java. It combines the advantages of optimistic-parallel simulation (i.e. use of parallelism for speed-up) and the process-oriented modeling (creation of an intuitive and structurally equivalent model). Another central objective of the development is to hide the internals of the optimistic-parallel simulation kernel from the modeler, in contrast to most existing PDES implementations. Instead, the implementation is encapsulated by interfaces, which resemble those of sequential simulation kernels, reducing the additional effort needed to create a suited model. A noteworthy aspect of the implementation is the reuse of a web application framework for retroactive modification of the Java bytecode, generated by the Java compiler. This bytecode rewriting solves in an elegant way the task of realizing coroutines, which are the base for the implementation of processes as needed by process-oriented simulation models.

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.