Fakultät für Mathematik, Informatik und Statistik - Digitale Hochschulschriften der LMU - Teil 01/02 Archiv

The Brown–Ravenhall model is used in quantum physics and chemistry to describe relativistic multiparticle systems, particularly atoms and molecules. In this dissertation we analyse some general properties of this model on the mathematically rigorous level. We show that under very general assumptions on the interaction potentials the essential spectrum of multiparticle Brown–Ravenhall operators is the right semiaxis starting from the minimal energy possible for the decompositions of the system into two clusters. This result, usually called HVZ theorem, is the fundamental starting point in the spectral analysis of multiparticle Hamiltonians with decaying potentials. Suppose now that the particles constituting the system repel each other but are confined by an external field decaying at infinity. In this situation we prove that the eigenfunctions corresponding to the eigenvalues below the essential spectrum decay exponentially. If some particles of the system are identical, the laws of quantum mechanics often require to reduce the operator to the subspace of functions which transform according to some irreducible representation of the group of permutation of identical particles. On the other hand, the interactions are often invariant under some rotations and reflections. We prove that both the HVZ theorem and the exponential decay of eigenfunctions hold true for operators reduced to the irreducible representations of the above groups. Our results are potentially important in further studies of the spectrum and in the scattering theory of Brown–Ravenhall operators.

Visions of the next generation Web such as the "Semantic Web" or the "Web 2.0" have triggered the emergence of a multitude of data formats. These formats have different characteristics as far as the shape of data is concerned (for example tree- vs. graph-shaped). They are accompanied by a puzzlingly large number of query languages each limited to one data format. Thus, a key feature of the Web, namely to make it possible to access anything published by anyone, is compromised. This thesis is devoted to versatile query languages capable of accessing data in a variety of Web formats. The issue is addressed from three angles: language design, common, yet uniform semantics, and common, yet uniform evaluation. % Thus it is divided in three parts: First, we consider the query language Xcerpt as an example of the advocated class of versatile Web query languages. Using this concrete exemplar allows us to clarify and discuss the vision of versatility in detail. Second, a number of query languages, XPath, XQuery, SPARQL, and Xcerpt, are translated into a common intermediary language, CIQLog. This language has a purely logical semantics, which makes it easily amenable to optimizations. As a side effect, this provides the, to the best of our knowledge, first logical semantics for XQuery and SPARQL. It is a very useful tool for understanding the commonalities and differences of the considered languages. Third, the intermediate logical language is translated into a query algebra, CIQCAG. The core feature of CIQCAG is that it scales from tree- to graph-shaped data and queries without efficiency losses when tree-data and -queries are considered: it is shown that, in these cases, optimal complexities are achieved. CIQCAG is also shown to evaluate each of the aforementioned query languages with a complexity at least as good as the best known evaluation methods so far. For example, navigational XPath is evaluated with space complexity O(q d) and time complexity O(q n) where q is the query size, n the data size, and d the depth of the (tree-shaped) data. CIQCAG is further shown to provide linear time and space evaluation of tree-shaped queries for a larger class of graph-shaped data than any method previously proposed. This larger class of graph-shaped data, called continuous-image graphs, short CIGs, is introduced for the first time in this thesis. A (directed) graph is a CIG if its nodes can be totally ordered in such a manner that, for this order, the children of any node form a continuous interval. CIQCAG achieves these properties by employing a novel data structure, called sequence map, that allows an efficient evaluation of tree-shaped queries, or of tree-shaped cores of graph-shaped queries on any graph-shaped data. While being ideally suited to trees and CIGs, the data structure gracefully degrades to unrestricted graphs. It yields a remarkably efficient evaluation on graph-shaped data that only a few edges prevent from being trees or CIGs.

Although the definition of symplectic field theory suggests that one has to count holomorphic curves in cylindrical manifolds equipped with a cylindrical almost complex structure, it is already well-known from Gromov-Witten theory that, due to the presence of multiply-covered curves, we in general cannot achieve transversality for all moduli spaces even for generic choices. In this thesis we treat the transversality problem of symplectic field theory in two important cases. In the first part of this thesis we are concerned with the rational symplectic field theory of Hamiltonian mapping tori, which is also called the Floer case. For this observe that in the general geometric setup for symplectic field theory, the contact manifolds can be replaced by mapping tori of symplectic manifolds with symplectomorphisms. While the cylindrical contact homology is given by the Floer homologies of powers of the symplectomorphism, the other algebraic invariants of symplectic field theory provide natural generalizations of symplectic Floer homology. For symplectically aspherical manifolds and Hamiltonian symplectomorphisms we study the moduli spaces of rational curves and prove a transversality result, which does not need the polyfold theory by Hofer, Wysocki and Zehnder and allows us to compute the full contact homology. The second part of this thesis is devoted to the branched covers of trivial cylinders over closed Reeb orbits, which are the trivial examples of punctured holomorphic curves studied in rational symplectic field theory. Since all moduli spaces of trivial curves with virtual dimension one cannot be regular, we use obstruction bundles in order to find compact perturbations making the Cauchy-Riemann operator transversal to the zero section and show that the algebraic count of elements in the resulting regular moduli spaces is zero. Once the analytical foundations of symplectic field theory are established, our result implies that the differential in rational symplectic field theory and contact homology is strictly decreasing with respect to the natural action filtration. After introducing additional marked points and differential forms on the target manifold we finally use our result to compute the second page of the corresponding spectral sequence for filtered complexes.

Kryptologie, die Wissenschaft von den Geheimschriften und ihrer Entschlüsselung, erfährt in der gegenwärtigen Zeit zunehmend praktische Bedeutung. Sie gewährleistet nicht nur Vertraulichkeit, Integrität und Authentizität beim Nachrichtenaustausch, sondern bestimmt auch die Sicherheit des elektronischen Geschäftsverkehrs, des Datenschutzes und ermöglicht digitale Signaturen. Gleichzeitig stützen sich moderne Verfahren der Kryptologie auf die Zahlentheorie, deren Grundlagen bereits in der Sekundarstufe I bereitgestellt werden. In der Vereinigung von mathematischen Inhalten, historischen Entwicklungen und aktuellen gesellschaftspolitischen Aspekten bietet Kryptologie vielfältige Einsatzmöglichkeiten für den Unterricht an allgemeinbildenden Schulen. Dass kryptologische Inhalte dennoch nicht in den Schulunterricht integriert sind, ist Anlass dieser Arbeit. Ausgehend vom Bildungs- und Erziehungsauftrag allgemeinbildender Schulen wird zunächst die Berechtigung eines Unterrichts in Kryptologie nachgewiesen. Anschließend wird dessen didaktischer Ort festgelegt, es werden geeignete Lerninhalte ausgewählt und in eine zeitliche Abfolge gebracht. In einer Unterrichtssequenz werden diese kryptologischen Lerninhalte didaktisch aufbereitet, auf Verständnisebene der Schüler transferiert und mit methodischen Hinweisen für Lehrkräfte versehen.

Nuclear magnetic resonance spectroscopy (NMR) is one of the most important methods for measuring the three-dimensional structure of biomolecules. Despite major progress in the NMR methodology, the solution of a protein structure is still a tedious and time-consuming task. The goal of this thesis is to develop bioinformatics methods which may strongly accelerate the NMR process. This work concentrates on a special type of measurements, the so-called chemical shifts. Chemical shifts are routinely measured at the beginning of a structure resolution process. As all data from the laboratory, chemical shifts may be error-prone, which might complicate or even circumvent the use of this data. Therefore, as the first result of the thesis, we present CheckShift, a method which automatically corrects a frequent error in NMR chemical shift data. However, the main goal of this thesis is the extraction of structural information hidden in chemical shifts. SimShift was developed as a first step in this direction. SimShift is the first approach to identify structural similarities between proteins based on chemical shifts. Compared to methods based on the amino acid sequence alone, SimShift shows its strength in detecting distant structural relationships. As a natural further development of the pairwise comparison of proteins, the SimShift algorithm is adapted for database searching. Given a protein, the improved algorithm, named SimShiftDB, searches a database of solved proteins for structurally homologue entries. The search is based only on the amino acid sequence and the associated chemical shifts. The detected similarities are additionally ranked based on calculations of statistical significance. Finally, the Chemical Shift Pipeline, the main result of this work, is presented. By combining automatic chemical shift error correction (CheckShift) and the database search algorithm (SimShiftDB), it is possible to achieve very high quality in 70% to 80% of the similarities identified. Thereby, only about 10% of the predictions are in error.

In dieser Arbeit wir ein pragmatischer Ansatz zur Typisierung, statischen Analyse und Optimierung von Web-Anfragespachen, speziell Xcerpt, untersucht. Pragmatisch ist der Ansatz in dem Sinne, dass dem Benutzer keinerlei Einschränkungen aus Entscheidbarkeits- oder Effizienzgründen auf modellierbare Typen gestellt werden. Effizienz und Entscheidbarkeit werden stattdessen, falls nötig, durch Vergröberungen bei der Typprüfung erkauft. Eine Typsprache zur Typisierung von Graph-strukturierten Daten im Web wird eingeführt. Modellierbare Graphen sind so genannte gewurzelte Graphen, welche aus einem Spannbaum und Querreferenzen aufgebaut sind. Die Typsprache basiert auf reguläre Baum Grammatiken, welche um typisierte Referenzen erweitert wurde. Neben wie im Web mit XML üblichen geordneten strukturierten Daten, sind auch ungeordnete Daten, wie etwa in Xcerpt oder RDF üblich, modellierbar. Der dazu verwendete Ansatz---ungeordnete Interpretation Regulärer Ausdrücke---ist neu. Eine operationale Semantik für geordnete wie ungeordnete Typen wird auf Basis spezialisierter Baumautomaten und sog. Counting Constraints (welche wiederum auf presburgerarithmetische Ausdrücke) basieren. Es wird ferner statische Typ-Prüfung und -Inferenz von Xcerpt Anfrage- und Konstrukttermen, wie auch Optimierung von Xcerpt Anfragen auf Basis von Typinformation eingeführt.

In der vorliegenden Arbeit wird eine Technik vorgestellt, die Software bereits aufgrund ihrer Modellbeschreibung in ihrem zeitlichen Verhalten bewertbar macht. Dazu wird eine Technik zur Beschreibung dynamischer Ausführungsmodelle für Zeitverhalten, sogenannte dynamische Performanz-Modelle, eingeführt. Ein Modellierungtechnik für Umgebungen wird beschrieben. Schließlich erlaubt die Definition einer zeitbehafteten Semantik die Bewertung einzelner Bearbeitungsabläufe. Mittels einer Petrinetzsemantik wird einerseits das Modellverhalten exakt festgelegt und andererseits ein Wohlgeformtheitsbegriff eingeführt, der einer späteren Werkzeugimplementierung dient. Die vorteilhaften technischen Eigenschaften dieses Entwurfes erlauben zudem eine Übersetzung aus UML-Aktivitätsdiagrammen. Anhand der Bewertung einzelner Abläufe wird das zeitliche Verhalten eines dynamischen Modells analysiert. Diese einzelnen Abläufe, sogenannte Szenarien, werden durch das Werkzeug bewertet. Jeweils ein Tripel aus einem dynamischen Modell, einem Szenario und einer passenden Umgebung läßt sich mit einen Zeitwert bewerten. Dynamischer Modelle können direkt aus UML-Aktivitätsdiagrammen erzeugt werden. Szenarien können graphisch editiert und Last- und Ressourcenmodellen aus Meßwerttabellen generiert werden. Die ermittelten Zeitwerte können dann graphisch aufbereitet und zur Beurteilung der dynamischen Eigenschaften herangezogen werden. Die hier entwickelten Modelle und eingesetzten formalen Spezifikationstechniken werden in der Werkzeugstudie vollständig gekapselt und müssen vom Werkzeuganwender nicht beherrscht werden. Somit stellt diese Arbeit auch ein Musterbeispiel für den Software-Entwurf unter Einbeziehung formaler Methoden dar.

Two recent technological advances have extended the diversity of domains and social contexts of Human-Computer Interaction: the embedding of computing capabilities into physical hand-held objects, and the emergence of large interactive surfaces, such as tabletops and wall boards. Both interactive surfaces and small computational devices usually allow for direct and space-multiplex input, i.e., for the spatial coincidence of physical action and digital output, in multiple points simultaneously. Such a powerful combination opens novel opportunities for the design of what are considered as hybrid interactions in this work. This thesis explores the affordances of physical interaction as resources for interface design of such hybrid interactions. The hybrid systems that are elaborated in this work are envisioned to support specific social and physical contexts, such as collaborative cooking in a domestic kitchen, or collaborative creativity in a design process. In particular, different aspects of physicality characteristic of those specific domains are explored, with the aim of promoting skill transfer across domains. irst, different approaches to the design of space-multiplex, function-specific interfaces are considered and investigated. Such design approaches build on related work on Graspable User Interfaces and extend the design space to direct touch interfaces such as touch-sensitive surfaces, in different sizes and orientations (i.e., tablets, interactive tabletops, and walls). These approaches are instantiated in the design of several experience prototypes: These are evaluated in different settings to assess the contextual implications of integrating aspects of physicality in the design of the interface. Such implications are observed both at the pragmatic level of interaction (i.e., patterns of users' behaviors on first contact with the interface), as well as on user' subjective response. The results indicate that the context of interaction affects the perception of the affordances of the system, and that some qualities of physicality such as the 3D space of manipulation and relative haptic feedback can affect the feeling of engagement and control. Building on these findings, two controlled studies are conducted to observe more systematically the implications of integrating some of the qualities of physical interaction into the design of hybrid ones. The results indicate that, despite the fact that several aspects of physical interaction are mimicked in the interface, the interaction with digital media is quite different and seems to reveal existing mental models and expectations resulting from previous experience with the WIMP paradigm on the desktop PC.

In recent years data sets have become increasingly more complex requiring more flexible instruments for their analysis. Such a flexible instrument is regression analysis based on a structured additive predictor which allows an appropriate modelling for different types of information, e.g.~by using smooth functions for spatial information, nonlinear functions for continuous covariates or by using effects for the modelling of cluster--specific heterogeneity. In this thesis, we review many important effects. Moreover, we place an emphasis on interaction terms and introduce a possibility for the simple modelling of a complex interaction between two continuous covariates. \\ Mainly, this thesis is concerned with the topic of variable and smoothing parameter selection within structured additive regression models. For this purpose, we introduce an efficient algorithm that simultaneously selects relevant covariates and the degree of smoothness for their effects. This algorithm is even capable of handling complex situations with many covariates and observations. Thereby, the validation of different models is based on goodness of fit criteria, like e.g.~AIC, BIC or GCV. The methodological development was strongly motivated by case studies from different areas. As examples, we analyse two different data sets regarding determinants of undernutrition in India and of rate making for insurance companies. Furthermore, we examine the performance or our selection approach in several extensive simulation studies.

In hoch entwickelten Wirtschaftssystemen unterliegen Banken einer besonderen Beaufsichtigung, da ein gut funktionierendes Finanzsystem die Grundlage einer soliden Wirtschaft darstellt. Insbesondere sind Banken verpflichtet, eine gesetzlich vorgegebene Eigenkapitaluntergrenze einzuhalten. Diese Grenze wurde in der Vergangenheit im Wesentlichen durch die Höhe der Bilanzaktiva bestimmt. Banken mussten für die aus diesen Positionen resultierenden Kredit- und Marktrisiken Eigenkapital vorhalten. Übrige Risiken wurden nur implizit abgedeckt. Durch die neue Baseler Eigenkapitalvereinbarung, die eine Empfehlung eines Ausschusses von Vertreten der Zentralbanken der großen Industrienationen darstellt und zurzeit in die jeweiligen nationalen Rechte umgesetzt wird, sollen nun unter anderem zusätzlich operationelle Risiken explizit mit Eigenkapital hinterlegt werden müssen. Zur Berechnung des notwendigen Eigenkapitals werden in der Vereinbarung drei verschiedene Ansätze aufgeführt, von denen zwei lediglich einfache und vermutlich risikounabhängige Berechnungsvorschriften darstellen; der dritte Ansatz jedoch - der Advanced Measurement Approach - kann bei entsprechender Ausgestaltung risikosensitiv sein, da er die Entwicklung und Verwendung selbst entwickelter Verfahren zur Bestimmung des Kapitals gestattet. Typischerweise werden bei solchen Verfahren Methoden aus der Versicherungswirtschaft verwendet, die Fragen zu Risiken von Prozessen, Personen, Technologie und externen Ereignissen bereits seit längerer Zeit zu beantworten versucht. Dazu werden die Ursachen der in der Vergangenheit aufgetretenen Verluste analysiert, um die aktuelle Gefahr zukünftiger Verluste zu ermitteln. Bei der Quantifizierung von Risiken in Banken müssen sehr hohe Quantile bestimmt werden, damit sichergestellt ist, dass das Unternehmen mit großer Wahrscheinlichkeit nicht zahlungsunfähig wird. Dies ist auch bei operationellen Risiken der Fall. Im Gegensatz zu Markt- oder Kreditrisiken stehen jedoch bei diesen nur relativ wenige Daten zur Verfügung. Dennoch wird in vielen zur Zeit verwendeten Modellen die Sensitivität der Ergebnisse aufgrund dieser sehr geringen Datenbasis nicht oder nicht ausreichend berücksichtigt. Die vorliegende Arbeit stellt ein Verfahren vor, um Konfidenzintervalle für geschätzte typische Risikogrößen wie z.B. einen Value-at-Risk oder den Expected Shortfall zu ermitteln. Die Anwendung wird dann anhand beispielhaft generierter Daten dargestellt, wobei die spezifischen Eigenheiten operationeller Risiken berücksichtigt werden. Dabei zeigt es sich, dass die bestimmten Konfidenzintervalle - abhängig von der für die Schätzungen verwendbaren Daten - mehrere Größenordnungen umfassen können. Bei der Interpretation der Daten und der daraus folgenden endgültigen Bestimmung von Mindestkapitalanforderungen für operationelle Risiken bei Banken müssen dann derartige Unschärfen berücksichtigt werden.

This thesis deals with data structures that are mostly useful in the area of string matching and string mining. Our main result is an O(n)-time preprocessing scheme for an array of n numbers such that subsequent queries asking for the position of a minimum element in a specified interval can be answered in constant time (so-called RMQs for Range Minimum Queries). The space for this data structure is 2n+o(n) bits, which is shown to be asymptotically optimal in a general setting. This improves all previous results on this problem. The main techniques for deriving this result rely on combinatorial properties of arrays and so-called Cartesian Trees. For compressible input arrays we show that further space can be saved, while not affecting the time bounds. For the two-dimensional variant of the RMQ-problem we give a preprocessing scheme with quasi-optimal time bounds, but with an asymptotic increase in space consumption of a factor of log(n). It is well known that algorithms for answering RMQs in constant time are useful for many different algorithmic tasks (e.g., the computation of lowest common ancestors in trees); in the second part of this thesis we give several new applications of the RMQ-problem. We show that our preprocessing scheme for RMQ (and a variant thereof) leads to improvements in the space- and time-consumption of the Enhanced Suffix Array, a collection of arrays that can be used for many tasks in pattern matching. In particular, we will see that in conjunction with the suffix- and LCP-array 2n+o(n) bits of additional space (coming from our RMQ-scheme) are sufficient to find all occ occurrences of a (usually short) pattern of length m in a (usually long) text of length n in O(m*s+occ) time, where s denotes the size of the alphabet. This is certainly optimal if the size of the alphabet is constant; for non-constant alphabets we can improve this to O(m*log(s)+occ) locating time, replacing our original scheme with a data structure of size approximately 2.54n bits. Again by using RMQs, we then show how to solve frequency-related string mining tasks in optimal time. In a final chapter we propose a space- and time-optimal algorithm for computing suffix arrays on texts that are logically divided into words, if one is just interested in finding all word-aligned occurrences of a pattern. Apart from the theoretical improvements made in this thesis, most of our algorithms are also of practical value; we underline this fact by empirical tests and comparisons on real-word problem instances. In most cases our algorithms outperform previous approaches by all means.

Microarrays can capture gene expression activity for thousands of genes simultaneously and thus make it possible to analyze cell physiology and disease processes on molecular level. The interpretation of microarray gene expression experiments profits from knowledge on the analyzed genes and proteins and the biochemical networks in which they play a role. The trend is towards the development of data analysis methods that integrate diverse data types. Currently, the most comprehensive biomedical knowledge source is a large repository of free text articles. Text mining makes it possible to automatically extract and use information from texts. This thesis addresses two key aspects, biomedical text mining and gene expression data analysis, with the focus on providing high-quality methods and data that contribute to the development of integrated analysis approaches. The work is structured in three parts. Each part begins by providing the relevant background, and each chapter describes the developed methods as well as applications and results. Part I deals with biomedical text mining: Chapter 2 summarizes the relevant background of text mining; it describes text mining fundamentals, important text mining tasks, applications and particularities of text mining in the biomedical domain, and evaluation issues. In Chapter 3, a method for generating high-quality gene and protein name dictionaries is described. The analysis of the generated dictionaries revealed important properties of individual nomenclatures and the used databases (Fundel and Zimmer, 2006). The dictionaries are publicly available via a Wiki, a web service, and several client applications (Szugat et al., 2005). In Chapter 4, methods for the dictionary-based recognition of gene and protein names in texts and their mapping onto unique database identifiers are described. These methods make it possible to extract information from texts and to integrate text-derived information with data from other sources. Three named entity identification systems have been set up, two of them building upon the previously existing tool ProMiner (Hanisch et al., 2003). All of them have shown very good performance in the BioCreAtIvE challenges (Fundel et al., 2005a; Hanisch et al., 2005; Fundel and Zimmer, 2007). In Chapter 5, a new method for relation extraction (Fundel et al., 2007) is presented. It was applied on the largest collection of biomedical literature abstracts, and thus a comprehensive network of human gene and protein relations has been generated. A classification approach (Küffner et al., 2006) can be used to specify relation types further; e. g., as activating, direct physical, or gene regulatory relation. Part II deals with gene expression data analysis: Gene expression data needs to be processed so that differentially expressed genes can be identified. Gene expression data processing consists of several sequential steps. Two important steps are normalization, which aims at removing systematic variances between measurements, and quantification of differential expression by p-value and fold change determination. Numerous methods exist for these tasks. Chapter 6 describes the relevant background of gene expression data analysis; it presents the biological and technical principles of microarrays and gives an overview of the most relevant data processing steps. Finally, it provides a short introduction to osteoarthritis, which is in the focus of the analyzed gene expression data sets. In Chapter 7, quality criteria for the selection of normalization methods are described, and a method for the identification of differentially expressed genes is proposed, which is appropriate for data with large intensity variances between spots representing the same gene (Fundel et al., 2005b). Furthermore, a system is described that selects an appropriate combination of feature selection method and classifier, and thus identifies genes which lead to good classification results and show consistent behavior in different sample subgroups (Davis et al., 2006). The analysis of several gene expression data sets dealing with osteoarthritis is described in Chapter 8. This chapter contains the biomedical analysis of relevant disease processes and distinct disease stages (Aigner et al., 2006a), and a comparison of various microarray platforms and osteoarthritis models. Part III deals with integrated approaches and thus provides the connection between parts I and II: Chapter 9 gives an overview of different types of integrated data analysis approaches, with a focus on approaches that integrate gene expression data with manually compiled data, large-scale networks, or text mining. In Chapter 10, a method for the identification of genes which are consistently regulated and have a coherent literature background (Küffner et al., 2005) is described. This method indicates how gene and protein name identification and gene expression data can be integrated to return clusters which contain genes that are relevant for the respective experiment together with literature information that supports interpretation. Finally, in Chapter 11 ideas on how the described methods can contribute to current research and possible future directions are presented.

This thesis is concerned with presenting and developing modeling approaches which allow for a time-varying effect of covariates by using time-varying coefficients. The different approaches are compared in simulation studies. Thereby, we investigate how well different components of the simulated models can be identified. The models performing best in the simulation study are then applied to data collected within the study "Improved Air Quality and its Influences on Short-Term Health Effects in Erfurt, Eastern Germany". One specific aspect in this analysis is to assess the necessity of a time-varying estimate compared to a more parsimonious, time-constant fit. A further topic is the estimation of time-varying coefficient models in the presence of measurement errors in the exposure variable. We specify a measurement error model and present methods to estimate parameters and measurement error variances of the model in the case of autocorrelated latent exposure as well as measurement errors. Furthermore, two methods adjusting for measurement errors in the context of time-varying coefficients are developed. The first one is based on a hierarchical Bayesian model and the Bayesian error correction principle. The second method is an extension of the well-known regression calibration approach to the case of autocorrelated data. The obtained estimated true values can then be included into the main model to assess the effect of the variable of interest. Finally, the approaches are again applied to the Erfurt data.