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

When web engineering methods are used for the development of web applications, models are created during the development process which describe the website. Using the information present in these models, it is possible to create usability tool support that is more advanced than current approaches, which do not rely on the presence of models. This dissertation presents ideas for tool support during different phases of the development, such as the implementation phase or the testing phase. For example, if a tool knows from a model that the audience of a website are teenagers, it can examine whether the words and sentences used on the website are likely to be understood by teenagers. An approach is presented to augment existing web engineering models with the additional information ("age" in this case) and to make it available to tools, e.g. via embedding it in HTML code. Two prototypes demonstrate the concepts for integrating usability tool support into web engineering.

In dieser Arbeit untersuchen wir Perelmans Ricci-Fluss mit Chirurgie auf geschlossenen 3–Mannigfaltigkeiten, deren Ausgangsmetrik invariant unter einer vorgegebenen glatten Wirkung einer endlichen Gruppe ist. Eine solche Metrik kann stets durch Mittelung einer beliebigen Riemannschen Metrik erzeugt werden, und wegen der Eindeutigkeit des Ricci-Flusses bleibt dieser bis zum Auftreten von Singularitäten invariant unter der Gruppenwirkung. Die technische Schwierigkeit besteht nun darin, Symmetrien der evolvierenden Metrik zu kontrollieren, wenn sich der Fluss einer Singularität nähert. Zu diesem Zweck konstruieren wir eine invariante singuläre S²–Blätterung auf dem Bereich der Mannigfaltigkeit, der von der Chirurgie betroffen ist. Insbesondere ermöglicht es diese, den Chirurgieprozess äquivariant durchzuführen und die Gruppenwirkung auf solchen Komponenten zu analysieren, die bei der Chirurgie komplett entfernt werden. Darüber hinaus lässt sich mit Hilfe der Blätterung beschreiben, wie die Gruppenwirkungen vor und nach der Chirurgie zusammenhängen. Dadurch lassen sich aus dem Langzeitverhalten des Ricci-Flusses und der Gruppenwirkung Rückschlüsse auf die ursprüngliche Wirkung ziehen. Als Anwendung zeigen wir, dass jede glatte endliche Gruppenwirkung auf einer geschlossenen geometrischen 3–dimensionalen Mannigfaltigkeit mit sphärischer, hyperbolischer oder (S²×R)–Geometrie verträglich mit der geometrischen Struktur ist, dass also eine invariante vollständige lokalhomogene Riemannsche Metrik existiert. Dies löst eine von William Thurston aufgestellte Frage zu Gruppenwirkungen auf geometrischen 3–Mannigfaltigkeiten, die für die übrigen fünf Geometrien bereits von Meeks und Scott gelöst wurde.

Die Arbeit behandelt verschiedene Modelle der Quantenelektrodynamik aus Sicht der Mathematik. Zunächst wird die Fortsetzung der Douglas-Kroll-Heß-Transformation für Systeme mit mehr als einem Teilchen diskutiert. Anschließend folgt eine ausführliche Untersuchung verschiedener Eigenschaften komplex dilatierter Dirac-Operatoren. Insbesondere werden positive und negative Spektralprojektionen sowie entsprechende Transformationsfunktionen eingeführt. Ferner wird der nicht-relativistische Limes solcher Operatoren untersucht. Diese Ergebnisse dienen als technische Vorbereitung zur Behandlung eines relativistischen Modells der Quantenelektrodynamik, sind jedoch auch von unabhängigem Interesse. In einem weiteren Kapitel wird das Dirac-Fock-Funktional im Falle schwacher Elektron-Elektron-Wechselwirkung behandelt. Insbesondere wird die Existenz von Lösungen der Dirac-Fock-Gleichungen mit bestimmten zusätzlichen Eigenschaften gezeigt. Es wird bewiesen, dass diese Lösungen gewisse Minimierungseigenschaften bezüglich des Dirac-Fock-Funktionals aufweisen. Schließlich wird die Wechselwirkung von Materie mit dem quantisierten elektromagnetischen Feld untersucht. Im Pauli-Fierz-Modell sowie in einem relativistischen Modell werden dabei obere und untere Schranken an die Lebensdauer angeregter Zustände bewiesen.

Due to the increase in CPU power and the ever increasing data storage capabilities, more and more data of all kind is recorded, including temporal data. Time series, the most prevalent type of temporal data are derived in a broad number of application domains. Prominent examples include stock price data in economy, gene expression data in biology, the course of environmental parameters in meteorology, or data of moving objects recorded by traffic sensors. This large amount of raw data can only be analyzed by automated data mining algorithms in order to generate new knowledge. One of the most basic data mining operations is the similarity query, which computes a similarity or distance value for two objects. Two aspects of such an similarity function are of special interest. First, the semantics of a similarity function and second, the computational cost for the calculation of a similarity value. The semantics is the actual similarity notion and is highly dependant on the analysis task at hand. This thesis addresses both aspects. We introduce a number of new similarity measures for time series data and show how they can efficiently be calculated by means of index structures and query algorithms. The first of the new similarity measures is threshold-based. Two time series are considered as similar, if they exceed a user-given threshold during similar time intervals. Aside from formally defining this similarity measure, we show how to represent time series in such a way that threshold-based queries can be efficiently calculated. Our representation allows for the specification of the threshold value at query time. This is for example useful for data mining task that try to determine crucial thresholds. The next similarity measure considers a relevant amplitude range. This range is scanned with a certain resolution and for each considered amplitude value features are extracted. We consider the change in the feature values over the amplitude values and thus, generate so-called feature sequences. Different features can finally be combined to answer amplitude-level-based similarity queries. In contrast to traditional approaches which aggregate global feature values along the time dimension, we capture local characteristics and monitor their change for different amplitude values. Furthermore, our method enables the user to specify a relevant range of amplitude values to be considered and so the similarity notion can be adapted to the current requirements. Next, we introduce so-called interval-focused similarity queries. A user can specify one or several time intervals that should be considered for the calculation of the similarity value. Our main focus for this similarity measure was the efficient support of the corresponding query. In particular we try to avoid loading the complete time series objects into main memory, if only a relatively small portion of a time series is of interest. We propose a time series representation which can be used to calculate upper and lower distance bounds, so that only a few time series objects have to be completely loaded and refined. Again, the relevant time intervals do not have to be known in advance. Finally, we define a similarity measure for so-called uncertain time series, where several amplitude values are given for each point in time. This can be due to multiple recordings or to errors in measurements, so that no exact value can be specified. We show how to efficiently support queries on uncertain time series. The last part of this thesis shows how data mining methods can be used to discover crucial threshold parameters for the threshold-based similarity measure. Furthermore we present a data mining tool for time series.

In this thesis, we prove that many asymptotic invariants of closed manifolds depend only on the image of the fundamental class under the classifying map of the universal covering. Examples include numerical invariants that reflect the asymptotic behaviour of the universal covering, like the minimal volume entropy and the spherical volume, as well as properties that are qualitative measures for the largeness of a manifold and its coverings, like enlargeability and hypersphericity. Another important class of invariants that share the above invariance property originates from universal volume bounds. The main example is the systolic constant, which encodes the relation between short noncontractible loops and the volume of a manifold. Further interesting examples are provided by the optimal constants in Gromov's filling inequalities, for which we show that they depend only on the dimension and orientability. Considering higher-dimensional generalizations of the systolic constant, a complete answer to the question about the existence of stable systolic inequalities is given. In the spirit of the results mentioned already, we also prove that the stable systolic constant depends only on the image of the fundamental class in a suitable Eilenberg-Mac Lane space.

Die vorliegende Arbeit befasst sich mit der Entwicklung interaktiver 3D-Anwendungen. Interaktive 3D-Grafik wird heutzutage in den verschiedensten Domänen eingesetzt, z. B. im e-Commerce-, Unterhaltungs- und Ausbildungsbereich. Dennoch stellt die Entwicklung einer umfangreicheren 3D-Anwendung nach wie vor eine Herausforderung dar. Programmcode und 3D-Inhalte werden i. d. R. von verschiedenen Entwicklern erstellt, die unterschiedliches Fachwissen besitzen und mit völlig verschiedenartigen Werkzeugen arbeiten. Diese Situation führt häufig zu Problemen bei der Integration der erstellten Anwendungskomponenten in ein komplexes interaktives 3D-Gesamtsystem. So können etwa Inkonsistenzen auftreten, die einen korrekten Zugriff des Programms auf die 3D-Inhalte zur Laufzeit verhindern. Zudem fehlen Konzepte und Werkzeuge zur Unterstützung einer strukturierten interdisziplinären 3D-Entwicklung. In der vorliegenden Arbeit wird ein neuartiger Lösungsansatz für die genannten Probleme vorgestellt. Es handelt sich dabei um eine Familie domänenspezifischer Sprachen, die für einen Einsatz in der Entwurfsphase vor der Implementierung im 3D-Entwicklungsprozess konzipiert wurden. Basissprache der Familie, die durch weitere Sprachkomponenten ergänzt wird, ist die Scene Structure and Integration Modelling Language (kurz SSIML). Mittels visueller Modelle lassen sich -- werkzeuggestützt -- Verknüpfungen zwischen Programmkomponenten und 3D-Inhalten spezifizieren. Durch die automatische Erzeugung von Codeskeletten aus einem Modell, die sowohl dem 3D-Designer als auch dem Programmierer als zu vervollständigende Vorlagen dienen, kann die Konsistenz zwischen den einzelnen Anwendungsbestandteilen sichergestellt werden. Neben der Verknüpfung von Programmcode und 3D-Inhalten sind die Strukturierung und Modularisierung von 3D-Inhalten, die aufgabenorientierte 3D-Visualisierung, 3D-Verhalten und Animation und Augmented Realitiy-Anwendungen weitere wichtige Aspekte, die durch die Mitglieder der SSIML-Sprachfamilie abgedeckt werden. Außerdem wird in der vorliegenden Arbeit ein 3D-Entwicklungsprozess skizziert, der einen sinnvollen Einbezug der vorgestellten Konzepte und Werkzeuge erlaubt.

Recursive partitioning methods from machine learning are being widely applied in many scientific fields such as, e.g., genetics and bioinformatics. The present work is concerned with the two main problems that arise in recursive partitioning, instability and biased variable selection, from a statistical point of view. With respect to the first issue, instability, the entire scope of methods from standard classification trees over robustified classification trees and ensemble methods such as TWIX, bagging and random forests is covered in this work. While ensemble methods prove to be much more stable than single trees, they also loose most of their interpretability. Therefore an adaptive cutpoint selection scheme is suggested with which a TWIX ensemble reduces to a single tree if the partition is sufficiently stable. With respect to the second issue, variable selection bias, the statistical sources of this artifact in single trees and a new form of bias inherent in ensemble methods based on bootstrap samples are investigated. For single trees, one unbiased split selection criterion is evaluated and another one newly introduced here. Based on the results for single trees and further findings on the effects of bootstrap sampling on association measures, it is shown that, in addition to using an unbiased split selection criterion, subsampling instead of bootstrap sampling should be employed in ensemble methods to be able to reliably compare the variable importance scores of predictor variables of different types. The statistical properties and the null hypothesis of a test for the random forest variable importance are critically investigated. Finally, a new, conditional importance measure is suggested that allows for a fair comparison in the case of correlated predictor variables and better reflects the null hypothesis of interest.

Knowledge Discovery in Databases (KDD) is the non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data. The core step of the KDD process is the application of a Data Mining algorithm in order to produce a particular enumeration of patterns and relationships in large databases. Clustering is one of the major data mining techniques and aims at grouping the data objects into meaningful classes (clusters) such that the similarity of objects within clusters is maximized, and the similarity of objects from different clusters is minimized. This can serve to group customers with similar interests, or to group genes with related functionalities. Currently, a challenge for clustering-techniques are especially high dimensional feature-spaces. Due to modern facilities of data collection, real data sets usually contain many features. These features are often noisy or exhibit correlations among each other. However, since these effects in different parts of the data set are differently relevant, irrelevant features cannot be discarded in advance. The selection of relevant features must therefore be integrated into the data mining technique. Since about 10 years, specialized clustering approaches have been developed to cope with problems in high dimensional data better than classic clustering approaches. Often, however, the different problems of very different nature are not distinguished from one another. A main objective of this thesis is therefore a systematic classification of the diverse approaches developed in recent years according to their task definition, their basic strategy, and their algorithmic approach. We discern as main categories the search for clusters (i) w.r.t. closeness of objects in axis-parallel subspaces, (ii) w.r.t. common behavior (patterns) of objects in axis-parallel subspaces, and (iii) w.r.t. closeness of objects in arbitrarily oriented subspaces (so called correlation cluster). For the third category, the remaining parts of the thesis describe novel approaches. A first approach is the adaptation of density-based clustering to the problem of correlation clustering. The starting point here is the first density-based approach in this field, the algorithm 4C. Subsequently, enhancements and variations of this approach are discussed allowing for a more robust, more efficient, or more effective behavior or even find hierarchies of correlation clusters and the corresponding subspaces. The density-based approach to correlation clustering, however, is fundamentally unable to solve some issues since an analysis of local neighborhoods is required. This is a problem in high dimensional data. Therefore, a novel method is proposed tackling the correlation clustering problem in a global approach. Finally, a method is proposed to derive models for correlation clusters to allow for an interpretation of the clusters and facilitate more thorough analysis in the corresponding domain science. Finally, possible applications of these models are proposed and discussed.

"In this thesis we follow two fundamental concepts from the {\it higher dimensional algebra}, the {\it categorification} and the {\it internalization}. From the geometric point of view, so far the most general torsors were defined in the dimension $n=1$, by {\it actions of categories and groupoids}. In the dimension $n=2$, Mauri and Tierney, and more recently Baez and Bartels from the different point of view, defined less general 2-torsors with the structure 2-group. Using the language of simplicial algebra, Duskin and Glenn defined actions and torsors internal to any Barr exact category $\E$, in an arbitrary dimension $n$. This actions are simplicial maps which are {\it exact fibrations} in dimensions $m \geq n$, over special simplicial objects called {\it n-dimensional Kan hypergroupoids}. The correspondence between the geometric and the algebraic theory in the dimension $n=1$ is given by the Grothendieck nerve construction, since the Grothendieck nerve of a groupoid is precisely a 1-dimensional Kan hypergroupoid. One of the main results is that groupoid actions and groupoid torsors become simplicial actions and simplicial torsors over the corresponding 1-dimensional Kan hypergroupoids, after the application of the Grothendieck nerve functor. The main result of the thesis is a generalization of this correspondence to the dimension $n=2$. This result is achieved by introducing two new algebraic and geometric concepts, {\it actions of bicategories} and {\it bigroupoid 2-torsors}, as a categorification and an internalization of actions of categories and groupoid torsors. We provide the classification of bigroupoid 2-torsors by {\it the second nonabelian cohomology} with coefficients in the structure bigroupoid. The second nonabelian cohomology is defined by means of the third new concept in the thesis, a {\it small 2-fibration} corresponding to an internal bigroupoid in the category $\E$. The correspondence between the geometric and the algebraic theory in the dimension $n=2$ is given by the Duskin nerve construction for bicategories and bigroupoids since the Duskin nerve of a bigroupoid is precisely a 2-dimensional Kan hypergroupoid. Finally, the main results of the thesis is that bigroupoid actions and bigroupoid 2-torsors become simplicial actions and simplicial 2-torsors over the corresponding 2-dimensional Kan hypergroupoids, after the application of the Duskin nerve functor."

In dieser Arbeit werden einige Aussagen über symplektische Strukturen auf 4-dimensionalen Mannigfaltigkeiten und Kontaktstrukturen auf 5-dimensionalen Mannigfaltigkeiten bewiesen. Wir untersuchen zunächst den Zusammenhang zwischen dem symplektischen und dem holomorphen Minimalitätsbegriff für Kählerflächen. Außerdem beweisen wir ein Resultat über die Irreduzibilität minimaler, einfach-zusammenhängender symplektischer 4- Mannigfaltigkeiten unter zusammenhängender Summe und eine Aussage über die konformen Systolen symplektischer 4-Mannigfaltigkeiten. Als nächstes betrachten wir die Konstruktion von differenzierbaren 4-dimensionalen Mannigfaltigkeiten durch die verallgemeinerte Fasersumme. Für den Fall, dass die Summation entlang eingebetteter Flächen mit trivialem Normalenbündel erfolgt, werden die ganzzahligen Homologiegruppen und im symplektischen Fall auch die kanonische Klasse der Fasersumme berechnet. Wir betrachten verschiedene Anwendungen, insbesondere hinsichtlich der Geographie einfach-zusammenhängender symplektischer 4-Mannigfaltigkeiten, deren kanonische Klasse durch eine vorgegebene natürliche Zahl teilbar ist. Wir zeigen auch, dass man mit geeigneten verzweigten Überlagerungen von komplexen Flächen vom allgemeinen Typ einfach-zusammenhängende algebraische Flächen konstruieren kann, deren kanonische Klasse eine vorgegebene Teilbarkeit besitzt. Im zweiten Teil der Arbeit betrachten wir die Boothby-Wang Konstruktion von Kontaktstrukturen auf Kreisbündeln über symplektischen Mannigfaltigkeiten. Zusammen mit den Resultaten über Geographie aus dem ersten Teil der Arbeit zeigen wir, dass es auf bestimmten einfach-zusammenhängenden 5-Mannigfaltigkeiten Kontaktstrukturen gibt, die nicht äquivalent sind, aber die in derselben (nicht-trivialen) Homotopieklasse von Fast-Kontaktstrukturen liegen.

This thesis studies the decidability of conversions in typed lambda-calculi, along with the algorithms allowing for this decidability. Our study takes in consideration conversions going beyond the traditional beta, eta, or permutative conversions (also called commutative conversions). To decide these conversions, two classes of algorithms compete, the algorithms based on rewriting, here the goal is to decompose and orient the conversion so as to obtain a convergent system, these algorithms then boil down to rewrite the terms until they reach an irreducible forms; and the "reduction free" algorithms where the conversion is decided recursively by a detour via a meta-language. Throughout this thesis, we strive to explain the latter thanks to the former.