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.

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.

Graphen sind in vielen Bereichen des Lebens zu finden, wobei wir speziell an Graphen in der Biologie interessiert sind. Knoten in solchen Graphen sind chemische Komponenten, Enzyme, Reaktionen oder Interaktionen, die durch Kanten miteinander verbunden sind. Eine effiziente Ausführung von Graphanfragen ist eine Herausforderung. In dieser Arbeit präsentieren wir GRIcano, ein System, das die effiziente Ausführung von Graphanfragen erlaubt. Wir nehmen an, dass Graphen in relationalen Datenbankmanagementsystemen (RDBMS) gespeichert sind. Als Graphanfragesprache schlagen wir eine erweiterte Version der Pathway Query Language (PQL) vor. Der Hauptbestandteil von GRIcano ist ein kostenbasierter Anfrageoptimierer. Diese Arbeit enthält Beiträge zu allen drei benötigten Komponenten des Optimierers, der relationalen Algebra, Implementierungen und Kostenmodellen. Die Operatoren der relationalen Algebra sind nicht ausreichend, um Graphanfragen auszudrücken. Daher stellen wir zuerst neue Operatoren vor. Wir schlagen den Erreichbarkeits-, Distanz-, Pfadlängen- und Pfadoperator vor. Zusätzlich geben wir Regeln für die Umformung von Ausdrücken an. Des Weiteren präsentieren wir Implementierungen für jeden vorgeschlagenen Operator. Der Hauptbeitrag ist GRIPP, eine Indexstruktur, die die effiziente Ausführung von Erreichbarkeitsanfragen auf sehr großen Graphen erlaubt. Wir zeigen, wie GRIPP und die rekursive Anfragestrategie genutzt werden können, um Implementierungen für alle Operatoren bereitzustellen. Die dritte Komponente von GRIcano ist das Kostenmodell, das Kardinalitätsabschätzungen der Operatoren und Kostenfunktionen für die Implementierungen benötigt. Basierend auf umfangreichen Experimenten schlagen wir in dieser Arbeit Funktionen dafür vor. Der neue Ansatz unserer Kostenmodelle ist, dass die Funktionen nur Kennzahlen der Graphen verwenden. Abschließend zeigen wir die Wirkungsweise von GRIcano durch Beispielanfragen auf echten biologischen Graphen. / Graphs occur in many areas of life. We are interested in graphs in biology, where nodes are chemical compounds, enzymes, reactions, or interactions that are connected by edges. Efficiently querying these graphs is a challenging task. In this thesis we present GRIcano, a system that efficiently executes graph queries. For GRIcano we assume that graphs are stored and queried using relational database management systems (RDBMS). We propose an extended version of the Pathway Query Language PQL to express graph queries. The core of GRIcano is a cost-based query optimizer. This thesis makes contributions to all three required components of the optimizer, the relational algebra, implementations, and cost model. Relational algebra operators alone are not sufficient to express graph queries. Thus, we first present new operators to rewrite PQL queries to algebra expressions. We propose the reachability, distance, path length, and path operator. In addition, we provide rewrite rules for the newly proposed operators in combination with standard relational algebra operators. Secondly, we present implementations for each proposed operator. The main contribution is GRIPP, an index structure that allows us to answer reachability queries on very large graphs. GRIPP has advantages over other existing index structures, which we review in this work. In addition, we show how to employ GRIPP and the recursive query strategy as implementation for all four proposed operators. The third component of GRIcano is the cost model, which requires cardinality estimates for operators and cost functions for implementations. Based on extensive experimental evaluation of our proposed algorithms we present functions to estimate the cardinality of operators and the cost of executing a query. The novelty of our approach is that these functions only use key figures of the graph. We finally present the effectiveness of GRIcano using exemplary graph queries on real biological networks.

Zufallsgraphen sind Graphen, die durch einen zufälligen Prozess erzeugt werden. Ein im Zusammenhang mit Zufallsgraphen häufig auftretendes Phänomen ist, dass sich die typischen Eigenschaften eines Graphen durch Hinzufügen einer relativ kleinen Anzahl von zufälligen Kanten radikal verändern. Wir betrachten den Zufallsgraphen G(n,p), der n Knoten enthält und in dem zwei Knoten unabhängig und mit Wahrscheinlichkeit p durch eine Kante verbunden sind. Erdös und Rényi zeigten, dass ein Graph für p = c/n und c < 1 mit hoher Wahrscheinlichkeit aus Komponenten mit O(log n) Knoten besteht. Für p = c/n und c > 1 enthält G(n,p) mit hoher Wahrscheinlichkeit genau eine Komponente mit Theta(n) Knoten, welche viel größer als alle anderen Komponenten ist. Dieser Punkt in der Entwicklung des Graphen, an dem sich die Komponentenstruktur durch eine kleine Erhöhung der Anzahl von Kanten stark verändert, wird Phasenübergang genannt. Wenn p = (1+epsilon)/n, wobei epsilon eine Funktion von n ist, die gegen 0 geht, sind wir in der kritischen Phase, welche eine der interessantesten Phasen der Entwicklung des Zufallsgraphen ist. In dieser Arbeit betrachten wir drei verschiedene Modelle von Zufallsgraphen. In Kapitel 4 studieren wir den Minimalgrad-Graphenprozess. In diesem Prozess werden sukzessive Kanten vw hinzugefügt, wobei v ein zuällig ausgewählter Knoten von minimalem Grad ist. Wir beweisen, dass es in diesem Graphenprozess einen Phasenübergang, und wie im G(n,p) einen Doppelsprung, gibt. Die zwei anderen Modelle sind Zufallsgraphen mit einer vorgeschriebenen Gradfolge und zufällige gerichtete Graphen. Für diese Modelle wurde bereits in den Arbeiten von Molloy und Reed (1995), Karp (1990) und Luczak (1990) gezeigt, dass es einen Phasenübergang bezüglich der Komponentenstruktur gibt. In dieser Arbeit untersuchen wir in Kapitel 5 und 6 die kritische Phase dieser Prozesse genauer, und zeigen, dass sich diese Modelle ähnlich zum G(n,p) verhalten. / Random graphs are graphs which are created by a random process. A common phenomenon in random graphs is that the typical properties of a graph change radically by the addition of a relatively small number of random edges. This phenomenon was first investigated in the seminal papers of Erdös and Rényi. We consider the graph G(n,p) which contains n vertices, and where any two vertices are connected by an edge independently with probability p. Erdös and Rényi showed that if p = c/n$ and c < 1, then with high probability G(n,p) consists of components with O(log n) vertices. If p = c/n$ and c>1, then with high probability G(n,p) contains exactly one component, called the giant component, with Theta(n) vertices, which is much larger than all other components. The point at which the giant component is formed is called the phase transition. If we let $p = (1+epsilon)/n$, where epsilon is a function of n tending to 0, we are in the critical phase of the random graph, which is one of the most interesting phases in the evolution of the random graph. In this case the structure depends on how fast epsilon tends to 0. In this dissertation we consider three different random graph models. In Chapter 4 we consider the so-called minimum degree graph process. In this process edges vw are added successively, where v is a randomly chosen vertex with minimum degree. We prove that a phase transition occurs in this graph process as well, and also that it undergoes a double jump, similar to G(n,p). The two other models we will consider, are random graphs with a given degree sequence and random directed graphs. In these models the point of the phase transition has already been found, by Molloy and Reed (1995), Karp (1990) and Luczak (1990). In Chapter 5 and 6 we investigate the critical phase of these processes, and show that their behaviour resembles G(n,p).

Chipkarten sind ein fester Bestandteil unseres täglichen Lebens, das immer stärker von der Zuverlässigkeit derartiger Sicherheitssysteme abhängt, zum Beispiel Bezahlkarten, elektronische Gesundheitskarten oder Ausweisdokumente. Eine Sicherheitspolitik beschreibt die wichtigsten Sicherheitsziele und Sicherheitsfunktionen eines Systems und bildet die Grundlage für dessen zuverlässige Entwicklung. In der Arbeit konzentrieren wir uns auf multi-applikative Chipkartenbetriebssysteme und betrachten neue zusätzliche Sicherheitsziele, die dem Schutz der Kartenanwendungen dienen. Da die Qualität des Betriebssystems von der umgesetzten Sicherheitspolitik abhängt, ist deren Korrektheit von entscheidender Bedeutung. Mit einer Formalisierung können Zweideutigkeiten in der Interpretation ausgeschlossen und formale Beweistechniken angewendet werden. Bisherige formale Verifikationen von Sicherheitspolitiken beinhalten im allgemeinen den Nachweis von Safety-Eigenschaften. Wir verlangen zusätzlich die Betrachtung von Security-Eigenschaften, wobei aus heutiger Sicht beide Arten von Eigenschaften stets getrennt in unterschiedlichen Formalismen verifiziert werden. Die Arbeit stellt eine gemeinsame Spezifikations- und Verifikationsmethodik mit Hilfe von Observer-Modellen vor, die sowohl den Nachweis von Safety-Eigenschaften in einem TLA-Modell als auch den Nachweis von Security-Eigenschaften kryptografischer Protokolle in einem induktiven Modell erlaubt. Da wir alle Spezifikationen und Verifikationen im Werkzeug VSE-II durchführen, bietet das formale Modell der Sicherheitspolitik nicht nur einen abstrakten Blick auf das System, sondern dient gleichzeitig als abstrakte Systemspezifikation, die es in weiteren Entwicklungsschritten in VSE-II zu verfeinern gilt. Die vorgestellte Methodik der Integration beider Systemmodelle in VSE-II führt somit zu einer erhöhten und nachweisbaren Qualität von Sicherheitspolitiken und von Sicherheitssystemen. / Security systems that use smart cards are nowadays an important part of our daily life, which becomes increasingly dependent on the reliability of such systems, for example cash cards, electronic health cards or identification documents. Since a security policy states both the main security objectives and the security functions of a certain security system, it is the basis for the reliable system development. This work focuses on multi-applicative smart card operating systems and addresses new security objectives regarding the applications running on the card. As the quality of the operating system is determined by the underlying security policy, its correctness is of crucial importance. A formalization of it first provides an unambiguous interpretation and second allows for the analysis with mathematical precision. The formal verification of a security policy generally requires the verification of so-called safety properties; but in the proposed security policy we are additionally confronting security properties. At present, safety and security properties of formal system models are verified separately using different formalisms. In this work we first formalize a security policy in a TLA system specification to analyze safety properties and then separately verify security properties using an inductive model of cryptographic protocols. We provide a framework for combining both models with the help of an observer methodology. Since all specifications and proofs are performed with the tool VSE-II, the verified formal model of the security policy is not just an abstract view on the security system but becomes its high level specification, which shall be refined in further development steps also to be performed with the tool. Hence, the integration of the two approaches within the tool VSE-II leads to a new quality level of security policies and ultimately of the development of security systems.

Flugzeug- und satellitengestützte Zeilenkameras ermöglichen eine sehr ökonomische Aufnahme von hoch aufgelösten Luftbildern mit großer Schwadbreite. Eine ungleichförmige Bewegung der Kamera kann sich auf die Bildqualität auswirken. Deswegen ist es unerlässlich, schnelle Orientierungsänderungen der Kamera mit angemessener Genauigkeit und Messrate zu erfassen. Deshalb ist es unerlässlich, die Orientierung der Kamera genau zu messen, um sicher zu stellen, dass die resultierenden Bilder in einem Nachbearbeitungsschritt geometrisch korrigiert werden können. Angemessene High-End-Navigationssysteme sind groß und teuer und ihre Genauigkeit und Messrate dennoch für viele denkbare Anwendungen unzureichend. Aus diesen Gründen besteht ein großes Interesse an Methoden zur Unterstützung der Orientierungsmessung durch die Nutzung optischer Informationen vom Hauptobjektiv bzw. Teleskop. In dieser Arbeit werden zwei unterschiedliche Verfahren vorgestellt, die es erlauben, schnelle Orientierungsänderungen der Kamera auf optischem Wege zu ermitteln. Ersteres basiert auf zusätzlichen Bildsensoren mit kleiner Fläche. Der optische Fluss auf diesen Bildsensoren wird ermittelt und zur Bestimmung von Orientierungsänderungen beliebiger Fernerkundungssysteme verwendet. Das zweite Verfahren beruht ausschließlich auf den Inhalten der Zeilenbilder und der gemessenen Kameratrajektorie. Hierfür macht sich das Verfahren die typische Geometrie multispektraler Zeilenkameras zu Nutze. Zunächst werden homologe Punkte in den möglicherweise stark verzerrten Zeilenbildern unterschiedlicher Spektralbänder extrahiert. Diese Punkte werden dann dazu benutzt, die Orientierungsänderungen der Kamera zu ermitteln. Schließlich wird gezeigt, dass es möglich ist, die absolute Orientierung einer luftgestützten Zeilenkamera anhand der optisch ermittelten Orientierungsänderungen hochgenau zu ermitteln. / Airborne and spaceborne line cameras allow a very economic acquisition of high resolution and wide swath images of the Earth. They generate two-dimensional images while rotating or translating, which causes a non-rigid image geometry. Nonuniform motion of the camera can negatively affect the image quality. Due to this, a key requirement for line cameras is that fast orientation changes have to be measured with a very high rate and precision. Therefore, it is essential to measure the camera’s orientation accurately to ensure that the resulting imagery products can be geometrically corrected in a later processing step. Adequate high-end measurement systems are large and expensive and their angular and temporal resolution can be still too low for many possible applications. Due to these reasons there is great interest in approaches to support the orientation measurement by using optical information received through the main optics or telescope. In this thesis two different approaches are presented that allow the determination of a line camera’s orientation changes optically. One approach to determine fast orientation changes is based on small auxiliary frame image sensors. The optical flow on these sensors is determined and used to derive orientation changes of any remote sensing system. The second approach does not require any additional sensors to determine orientation changes. It relies only on the images of a line camera and a rough estimate of its trajectory by taking advantage of the typical geometry of multi-spectral line cameras. In a first step homologous points are detected within the distorted images of different spectral bands. These points are used to calculate the orientation changes of the camera with a high temporal and angular resolution via bundle adjustment. Finally it is shown how the absolute exterior orientation of an airborne line camera can completely be derived from the optically determined orientation changes.

Verlässliche Dienstbereitstellung ist eines der wichtigsten Ziele in modernen Netzwerken. Da Anbieter und Nutzer Teil einer Informations und Kommunikationstechnologie (IKT) Infrastruktur sind, wird die Verlässlichkeit der Dienste je nach Position der Aktoren variieren, so wie sich die für die Bereitstellung nötigen IKT Geräte ändern. Wir stellen zwei Ansätze zur Quantifizierung nutzerspezifischer Dienstverlässlichkeit vor. Der erste, modellgetriebene Ansatz berechnet momentane Dienstverfügbarkeit. Aus Modellen des Dienstes, der Infrastruktur und einer Abbildung zwischen den beiden, welche die Aktoren der Dienstkommunikation beschreibt, werden durch eine Serie von Modelltransformationen automatisiert Verfügbarkeitsmodelle generiert. Die Realisierbarkeit des Ansatzes wird anhand von Diensten im Netzwerk der Universität Lugano, Schweiz, gezeigt. Der zweite Ansatz behandelt die Responsivität der Dienstfindung, die Wahrscheinlichkeit innerhalb einer Frist Dienstinstanzen zu finden, unter der Annahme von Fehlern. Dies stellt den Hauptteil dieser Arbeit dar. Eine Hierarchie stochastischer Modelle wird vorgestellt, die nutzerspezifische Responsivität auf Basis von Messdaten der Routingebene berechnet. Umfangreiche Experimente wurden im Distributed Embedded Systems (DES) Funktestbett der Freien Universität Berlin durchgefürt. Diese zeigen Probleme aktueller Dienstfindungsprotokolle in modernen, dynamischen Netzwerken. Gleichzeitig dienen sie der Validierung der vorgestellten Modelle. Beide Ansätze zeigen, daß die Verlässlichkeit der Dienstbereitstellung in der Tat deutlich mit der Position von Nutzern und Anbietern variiert, sogar in hochverfügbaren Kabelnetzwerken. Die Ansätze ermöglichen die Optimierung von Dienstnetzwerken anhand bekannter oder erwarteter Nutzungsmuster. Zudem antizipieren sie neuartige Verlässlichkeitsmodelle, welche Dienstfindung, zeitige Bereitstellung, Platzierung und Nutzung kombinieren; Gebiete, die bisher im Allgemeinen getrennt behandelt wurden. / Dependability of service provision is one of the primary goals in modern networks. Since providers and clients are part of a connecting Information and Communications Technology (ICT) infrastructure, service dependability varies with the position of actors as the ICT devices needed for service provision change. We present two approaches to quantify user-perceived service dependability. The first is a model-driven approach to calculate instantaneous service availability. Using input models of the service, the infrastructure and a mapping between the two to describe actors of service communication, availability models are automatically created by a series of model to model transformations. The feasibility of the approach is demonstrated using exemplary services in the network of University of Lugano, Switzerland. The second approach aims at the responsiveness of the service discovery layer, the probability to find service instances within a deadline even in the presence of faults, and is the main part of this thesis. We present a hierarchy of stochastic models to calculate user-perceived responsiveness based on monitoring data from the routing layer. Extensive series of experiments have been run on the Distributed Embedded Systems (DES) wireless testbed at Freie Universität Berlin. They serve both to demonstrate the shortcomings of current discovery protocols in modern dynamic networks and to validate the presented stochastic models. Both approaches demonstrate that the dependability of service provision indeed differs considerably depending on the position of service clients and providers, even in highly reliable wired networks. The two approaches enable optimization of service networks with respect to known or predicted usage patterns. Furthermore, they anticipate novel service dependability models which combine service discovery, timeliness, placement and usage, areas that until now have been treated to a large extent separately.

Die vorliegende Dissertation beinhaltet eine umfassende Untersuchung der Entscheidbarkeit und Komplexität der Probleme, die sich durch eine statische Analyse von monadischem Datalog auf endlichen gefärbten Bäumen stellen. Statische Analyse bedeutet hierbei Anfrageoptimierung ohne Blick auf konkrete Instanzen, aber mit Rücksicht auf deren zugrunde liegende Struktur. Im Kern beinhaltet dies die Lösung der drei folgenden Probleme: das Leerheitsproblem (die Frage, ob eine Anfrage auf jeder Instanz ein leeres Ergebnis liefert), das Äquivalenzproblem (die Frage, ob zwei Anfragen auf jeder Instanz das gleiche Ergebnis liefern) und das Query-Containment-Problem (die Frage, ob das Ergebnis der einen Anfrage auf jeder Datenbank im Ergebnis der anderen Anfrage enthalten ist). Von Interesse ist dabei, ob die Fragen für eine gegebene Anfragesprache entscheidbar sind und wenn ja, welche Komplexität ihnen innewohnt. Wir betrachten diese Probleme für monadisches Datalog auf unterschiedlichen Repräsentationen für endliche gefärbte Bäume. Hierbei unterscheiden wir zwischen ungeordneten und geordneten Bäumen, welche die Achsen child bzw. firstchild und nextsibling und deren Erweiterung um die descendant-Achse nutzen. Außerdem unterscheiden wir Alphabete mit und ohne Rang. Monadisches Datalog ist eine Anfragesprache, die in Abhängigkeit vom gewählten Schema die Ausdrucksstärke der monadischen Logik zweiter Stufe (MSO) erreicht und dennoch effizient ausgewertet werden kann. Wir zeigen, dass unter in der Datenbanktheorie üblichen Mengensemantik die drei genannten Probleme für alle Schemata ohne descendant-Achse EXPTIME-vollständig sind und lösbar in 2EXPTIME, falls die descendant-Achse involviert ist. Eine passende untere Schranke wird für fast alle Schemata gezeigt. Unter Multimengensemantik lassen sich die obigen Ergebnisse für das Leerheitsproblem übertragen, während das Query-Containment-Problem für alle betrachteten Schemata unentscheidbar ist. / This thesis provides a comprehensive investigation into the decidability and complexity of the fundamental problems entailed by static analysis of monadic datalog on finite labeled trees. Static analysis is used for optimizing queries without considering concrete database instances but exploiting information about the represented structure. Static analysis relies on three basic decision problems. First, the emptiness problem, whose task is to decide whether a query returns the empty result on every database. Second, the equivalence problem asking if the result of two given queries always coincides on every database. And finally, the query containment problem where it is to decide whether on every database a given query produces a subset of the results of a second given query. We are interested in finding out whether these problems are decidable and, if so, what their complexity is. We consider the aforementioned problems for monadic datalog on different representations of finite labeled trees. We distinguish unordered and ordered trees which use the axis child, as well as the axes firstchild and nextsibling, respectively. An extension of the schemas by the descendant-axis is also considered. Furthermore, we distinguish ranked and unranked labeling alphabets. Depending on the schema, the query language monadic datalog can reach the expressive power of monadic second order logic but remains efficiently evaluable. Under set semantics, we show EXPTIME-completness for all used schemas where the descendant-axis is omitted. If the descendant-axis is involved, we present an algorithm that solves the problem within 2-fold exponential time. A matching lower bound is proven for virtually all schemas. Finally, we prove that the complexity of the emptiness problem of monadic datalog on finite trees under bag semantics is the same as under set semantics. Furthermore, we show that the query containment problem of monadic datalog under bag semantics is undecidable in general.

Erdbeben gehören zu den zerstörerischsten Naturgefahren auf diesem Planeten. Obwohl Erdbeben seit Jahrtausenden dokumentiert sing, bleiben viele Fragen zu Erdbeben unbeantwortet. Eine Frage ist die Vorhersagbarkeit von Brüchen: Inwieweit ist es möglich, die endgültige Größe eines Bebens zu bestimmen, bevor der zugrundeliegende Bruchprozess endet? Diese Frage ist zentral für Frühwarnsysteme. Die bisherigen Forschungsergebnisse zur Vorhersagbarkeit von Brüchen sind widersprüchlich. Die Menge an verfügbaren Daten für Erdbebenforschung wächst exponentiell und hat den Tera- bis Petabyte-Bereich erreicht. Während viele klassische Methoden, basierend auf manuellen Datenauswertungen, hier ihre Grenzen erreichen, ermöglichen diese Datenmengen den Einsatz hochparametrischer Modelle und datengetriebener Analysen. Insbesondere ermöglichen sie den Einsatz von maschinellem Lernen und deep learning. Diese Doktorarbeit befasst sich mit der Entwicklung von Methoden des maschinellen Lernens zur Untersuchung zur Erbebenanalyse. Wir untersuchen zuerst die Kalibrierung einer hochpräzisen Magnitudenskala in einem post hoc Scenario. Nachfolgend befassen wir uns mit Echtzeitanalyse von Erdbeben mittels deep learning. Wir präsentieren TEAM, eine Methode zur Frühwarnung. Auf TEAM aufbauend entwickeln wir TEAM-LM zur Echtzeitschätzung von Lokation und Magnitude eines Erdbebens. Im letzten Schritt untersuchen wir die Vorhersagbarkeit von Brüchen mittels TEAM-LM anhand eines Datensatzes von teleseismischen P-Wellen-Ankünften. Dieser Analyse stellen wir eine Untersuchung von Quellfunktionen großer Erdbeben gegenüber. Unsere Untersuchung zeigt, dass die Brüche großer Beben erst vorhersagbar sind, nachdem die Hälfte des Bebens vergangen ist. Selbst dann können weitere Subbrüche nicht vorhergesagt werden. Nichtsdestotrotz zeigen die hier entwickelten Methoden, dass deep learning die Echtzeitanalyse von Erdbeben wesentlich verbessert. / Earthquakes are among the largest and most destructive natural hazards known to humankind. While records of earthquakes date back millennia, many questions about their nature remain open. One question is termed rupture predictability: to what extent is it possible to foresee the final size of an earthquake while it is still ongoing? This question is integral to earthquake early warning systems. Still, research on this question so far has reached contradictory conclusions. The amount of data available for earthquake research has grown exponentially during the last decades reaching now tera- to petabyte scale. This wealth of data, while making manual inspection infeasible, allows for data-driven analysis and complex models with high numbers of parameters, including machine and deep learning techniques. In seismology, deep learning already led to considerable improvements upon previous methods for many analysis tasks, but the application is still in its infancy. In this thesis, we develop machine learning methods for the study of rupture predictability and earthquake early warning. We first study the calibration of a high-confidence magnitude scale in a post hoc scenario. Subsequently, we focus on real-time estimation models based on deep learning and build the TEAM model for early warning. Based on TEAM, we develop TEAM-LM, a model for real-time location and magnitude estimation. In the last step, we use TEAM-LM to study rupture predictability. We complement this analysis with results obtained from a deep learning model based on moment rate functions. Our analysis shows that earthquake ruptures are not predictable early on, but only after their peak moment release, after approximately half of their duration. Even then, potential further asperities can not be foreseen. While this thesis finds no rupture predictability, the methods developed within this work demonstrate how deep learning methods make a high-quality real-time assessment of earthquakes practically feasible.

Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist. / This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.