Die Bestimmung der Ähnlichkeit von molekularen Strukturen und das Clustern solcher Strukturen gemäß Ähnlichkeit sind zwei zentrale Fragen im Wirkstoffdesign. Die Arbeit beschreibt im ersten Teil zwei neue Verfahren zum Vergleich von Molekülen auf 3-dimensionale Ähnlichkeit. Der erste Algorithmus benutzt als Eingabe nur die Koordinaten der Atome der zu vergleichenden Moleküle. Wir können zeigen, daß eine rein geometrische Zielfunktion in der Lage ist, Wirkungsähnlichkeit von Substanzen vorherzusagen, und daß der Algorithmus geeignet ist, Ähnlichkeiten zu finden, die mit bisherigen, einfacheren Methoden nicht gefunden werden konnten. Das zweite Verfahren nutzt zusätzlich noch die Bindungsstruktur der Eingabemoleküle. Es ist flexibel, d.h. alle Konformere der Moleküle werden simultan behandelt. Wir erhalten ein sehr schnelles Verfahren, das bei geeigneter Parametereinstellung auch beweisbar optimale Lösungen liefert. Für praktisch relevante Anwendungen erreichen wir erstmals Laufzeiten, die selbst das Durchsuchen großer Datenbanken ermöglichen. Im zweiten Teil beschreiben wir zwei Methoden, eine Menge von molekularen Strukturen so zu organisieren, daß die Suche nach geometrisch ähnlichen deutlich schneller durchgeführt werden kann als durch lineare Suche. Nach Analyse der Daten mit graphentheoretischen Methoden finden hierarchische Verfahren und repräsentantenbasierte Ansätze ihre Anwendung. Schließlich geben wir einen neuen Algorithmus zum Biclustern von Daten an, einem Problem, das bei der Analyse von Genexpressionsdaten eine wichtige Rolle spielt. Mit graphentheoretischen Methoden konstruieren wir zunächst deterministisch Obermengen von Lösungen, die danach heuristisch ausgedünnt werden. Wir können zeigen, daß dieser neue Ansatz bisherige, vergleichbare z.T. deutlich überbietet. Seine prinzipielle Einfachheit läßt anwendungsbezogene Modifikationen leicht zu. / Two important questions in drug design are the following: "How to compute the similarity of two molecules?" and "How to cluster molecules by similarity?" In the first part we describe two different approaches to compare molecules for 3D-similarity. The first algorithm just uses the 3D coordinates of the atoms as input. We show that this algorithm is able to detect similar activity or similar adverse reaction, even with a simple purely geometry based scoring function. Compared to previous simpler approaches more interesting hits are found. The connectivity structures of the molecular graphs are used by the second algorithm as additional input. This fully flexible approach -- conformers of the molecules are treated simultaneously -- may even find provably optimal solutions. Parameter settings for practically relevant instances allow running times that make it possible to even search large databases. The second part describes two methods to search a database of molecular structures. After analyzing the data with graph theoretical methods two algorithms for two different ranges of similarity are designed. Scanning the database for structures similar to a given query can be accelerated considerably. We use hierarchical methods and dominating set techniques. Finally we propose a new biclustering algorithm. Biclustering problems recently appeared mainly in the context of analysing gene expression data. Again graph theoretical methods are our main tools. In our model biclusters correspond to dense subgraphs of certain bipartite graphs. In a first phase the algorithm deterministically finds supersets of solution candidates. Thinning out these sets by heuristical methods leads to solutions. This new algorithm outperforms former comparable methods and its simple structure make it easy to customize it for practical applications.

Die mobile Robotik stellt ein sehr junges und komplexes Forschungsfelder unserer Zeit dar. Innerhalb der letzten Jahrzehnte wurde es Robotern möglich, sich innerhalb ihrer Umgebung zu bewegen, zu navigieren und mit ihrer Umwelt zu interagieren. Aufgrund der Tatsache, dass die Welt von Unsicherheit geprägt ist und ein Roboter immer nur partielle Information über sie erhalten kann, wurden probabilistische Navigationsverfahren entwickelt, mit denen sich Roboter lokalisieren und Objekte ihrer Umgebung modellieren können. Weiterhin wurden in letzter Zeit Verfahren untersucht, die die kooperative Exploration der Umgebung durch eine Gruppe von Robotern zum Ziel haben. In der vorliegenden Arbeit wird ein neuartiges Konzept, welches sich Perzeptrelationen für die kooperative Umweltmodellierung zu Nutze macht, vorgestellt und evaluiert. Einen zweiten Beitrag der Arbeit stellen constraintbasierte Lokalisierungstechniken dar, die es einem oder mehreren Robotern auf effiziente Art und Weise ermöglichen, sich zu lokalisieren und ihre Umwelt zu modellieren. / Mobile autonomous robotics is a very young and complex field of research. Only in recent decades have robots become able to explore, to move, navigate and to interact with their environment. Since the world is uncertain and since robots can only gain partial information about it, probabilistic navigation algorithms have become very popular whenever a robot has to localize itself or surrounding objects. Furthermore, cooperative exploration and localization approaches have become very relevant lately, as robots begin to act not just alone but in groups. Within this thesis a new approach using the concept of spatial percept-relations for cooperative environment modeling is presented and evaluated. As a second contribution, constraint based localization techniques will be introduced for having a robot or a group of robots efficiently localized and to model their environment.

Die vorliegende Arbeit besteht aus zwei Teilen. Der erste Teil der Arbeit befasst sich mit unteren Schranken für approximative Steinerbaumalgorithmen. Ein Steinerbaum ist ein kürzester Teilgraph, der eine gegebene Teilmenge der Knoten eines Graphen spannt. Das Berechnen eines Steinerbaumes ist ein klassisches NP-schweres Problem, und es existieren mehrere Approximationsalgorithmen, wobei bei den meisten Algorithmen die Approximationsgüte nur durch untere und obere Schranken eingegrenzt werden kann. Für einige dieser Algorithmen werden in dieser Arbeit Instanzen vorgestellt, welche die unteren Schranken verbessern. Für den Relativen Greedy Algorithmus wird außerdem ein Verfahren vorgestellt, mit dem die Güte des Algorithmus eingeschränkt auf die Graphenklasse mit k Terminalen auf einen beliebigen Faktor genau bestimmt werden kann. Der zweite Teil der Arbeit widmet sich vollständig bipartiten Subgraphen mit gleicher Partitionsgrößse, sogenannten balancierten Bicliquen. Seit langem ist bekannt, dass in dichten bipartiten Graphen balancierte Bicliquen mit Omega(log(n)) Knoten existieren, aber es ist unbekannt, ob und wie diese in polynomieller Zeit konstruiert werden können. Der zweite Teil liefert dazu einen Beitrag, indem ein polynomieller Algorithmus vorgestellt wird, der in hinreichend großen dichten bipartiten Graphen eine balancierte Biclique mit Omega(sqrt(log(n))) Knoten konstruiert. / This thesis consists of two parts. The first part is concerned with lower bounds for approximating Steiner trees. The Steiner tree problem is to find a shortest subgraph that spans a given set of vertices in a graph and is a classical NP-hard problem. Several approximation algorithms exist, but for most algorithms only lower and upper bounds for the approximation ratio are known. For some of these algorithms we present instances which improve the lower bounds. When the problem is restricted to the class of graphs with k terminals, we also present a method which can be used to determine the approximation ratio of the Relative Greedy Algorithm with arbitrary precision. The second part is about balanced bicliques, i.e. complete bipartite subgraphs with equal partition sizes. It has been known for a long time that every dense bipartite graph contains a balanced biclique of size Omega(log(n)), but whether and how such a biclique can be constructed in polynomial time is still unknown. Our contribution to this problem is a polynomial time algorithm which constructs a balanced biclique of size Omega(sqrt(log(n))) in sufficiently large and dense bipartite graphs.

Datalog ist die relationale Variante der logischen Programmierung und ist eine Standard-Abfragesprache in der Datenbankentheorie geworden. Die Programmkomplexität von Datalog im bisherigen Hauptanwendungsgebiet, auf endlichen Strukturen, ist bekanntermassen in EXPTIME. Wir untersuchen die Komplexität von Datalog auf unendlichen Strukturen, motiviert durch mögliche Anwendungen von Datalog auf unendlichen Strukturen (z.B. linearen Ordnungen) im zeitlichen und räumlichen Schliessen, aber auch durch das aufkommende Interesse an unendlichen Strukturen bei verwandten theoretischen Problemen, wie Constraint Satisfaction Problems (CSP): Im Gegensatz zu endlichen Strukturen können Datalog-Berechnungen auf unendlichen Strukturen unendlich lange dauern, was zur Unentscheidbarkeit von Datalog auf unendlichen Strukturen führen kann. Aber auch in den entscheidbaren Fällen kann die Komplexität von Datalog auf unendlichen Strukturen beliebig hoch sein. Im Hinblick auf dieses Ergebnis widmen wir uns dann unendlichen Strukturen mit der niedrigsten Komplexität von Datalog: Wir zeigen, dass Datalog auf linearen Ordnungen (auch dichte und diskrete, mit oder ohne Konstanten und sogar gefärbte) und Baumordnungen EXPTIME-vollständig ist. Für die Bestimmung der oberen Schranke werden Werkzeuge für Datalog auf Ordnungen eingeführt: Ordnungstypen, Abstandstypen und typdisjunkte Programme. Die Typkonzepte liefern eine endliche Beschreibung der unendlichen Programmergebnisse und könnten auch für praktische Anwendungen von Interesse sein. Wir erzeugen spezielle typdisjunkte Programme, die sich ohne Rekursion lösen lassen. Ein Transfer unserer Methoden auf CSPs zeigt, dass CSPs auf unendlichen Strukturen mit beliebig hoher Zeitkomplexität vorkommen, wie Datalog. / Datalog is the relational variant of logic programming and has become a standard query language in database theory. The (program) complexity of datalog in its main context so far, on finite databases, is well known to be in EXPTIME. We research the complexity of datalog on infinite databases, motivated by possible applications of datalog to infinite structures (e.g. linear orders) in temporal and spatial reasoning on one hand and the upcoming interest in infinite structures in problems related to datalog, like constraint satisfaction problems: Unlike datalog on finite databases, on infinite structures the computations may take infinitely long, leading to the undecidability of datalog on some infinite structures. But even in the decidable cases datalog on infinite structures may have arbitrarily high complexity, and because of this result, we research some structures with the lowest complexity of datalog on infinite structures: Datalog on linear orders (also dense or discrete, with and without constants, even colored) and tree orders has EXPTIME-complete complexity. To achieve the upper bound on these structures, we introduce a tool set specialized for datalog on orders: Order types, distance types and type disjoint programs. The type concept yields a finite representation of the infinite program results, which could also be of interest for practical applications. We create special type disjoint versions of the programs allowing to solve datalog without the recursion inherent in each datalog program. A transfer of our methods shows that constraint satisfaction problems on infinite structures occur with arbitrarily high time complexity, like datalog.

"Die Bedeutung eines Wortes ist sein Gebrauch in der Sprache". Ludwig Wittgenstein führte diese Idee in der ersten Hälfte des 20. Jahrhunderts in die Philosophie ein und in verwandten Disziplinen wie der Psychologie und Linguistik setzte sich vor allem in den letzten Jahrzehnten die Ansicht durch, dass natürliche Sprache ein dynamisches System arbiträrer und kulturell gelernter Konventionen ist. Forscher um Luc Steels übertrugen diesen Sprachbegriff seit Ende der 90er Jahre auf das Gebiet der Künstlichen Intelligenz, indem sie zunächst Software-Agenten und später Robotern mittels sogenannter Sprachspiele gemeinsame Kommunikationssysteme bilden liessen, ohne dass Agenten im Voraus mit linguistischem und konzeptionellen Wissen ausgestattet werden. Die vorliegende Arbeit knüpft an diese Forschung an und untersucht vertiefend die Selbstorganisation von geteiltem lexikalischen Wissen in humanoiden Robotern. Zentral ist dabei das Konzept der "referential uncertainty", d.h. die Schwierigkeit, die Bedeutung eines bisher unbekannten Wortes aus dem Kontext zu erschliessen. Ausgehend von sehr einfachen Modellen der Lexikonbildung untersucht die Arbeit zunächst in einer simulierten Umgebung und später mit physikalischen Robotern systematisch, wie zunehmende Komplexität kommunikativer Interaktionen komplexere Lernmodelle und Repräsentationen erfordert. Ein Ergebnis der Evaluierung der Modelle hinsichtlich Robustheit und Übertragbarkeit auf Interaktionszenarien mit Robotern ist, dass die in der Literatur vorwiegenden selektionistischen Ansätze schlecht skalieren und mit der zusätzlichen Herausforderung einer Verankerung in visuellen Perzeptionen echter Roboter nicht zurecht kommen. Davon ausgehend wird ein alternatives Modell vorgestellt. / "The meaning of a word is its use in the language". In the first half of the 20th century Ludwig Wittgenstein introduced this idea into philosophy and especially in the last few decades, related disciplines such as psychology and linguistics started embracing the view that that natural language is a dynamic system of arbitrary and culturally learnt conventions. From the end of the nineties on, researchers around Luc Steels transferred this notion of communication to the field of artificial intelligence by letting software agents and later robots play so-called language games in order to self-organize communication systems without requiring prior linguistic or conceptual knowledge. Continuing and advancing that research, the work presented in this thesis investigates lexicon formation in humanoid robots, i.e. the emergence of shared lexical knowledge in populations of robotic agents. Central to this is the concept of referential uncertainty, which is the difficulty of guessing a previously unknown word from the context. First in a simulated environments and later with physical robots, this work starts from very simple lexicon formation models and then systematically analyzes how an increasing complexity in communicative interactions leads to an increasing complexity of representations and learning mechanisms. We evaluate lexicon formation models with respect to their robustness, scaling and their applicability to robotic interaction scenarios and one result of this work is that the predominating approaches in the literature do not scale well and are not able to cope with the challenges stemming from grounding words in the real-world perceptions of physical robots. In order to overcome these limitations, we present an alternative lexicon formation model and evaluate its performance.

Wir betrachten offene Systeme; Systeme mit Schnittstelle und Verhalten in Form eines Protokolls. Offener Systeme interagieren durch den Austausch von Nachrichten. Die Interaktion ist korrekt, wenn die interagierende offenen Systeme terminieren können. Die korrekte Interaktion unabhängig entwickelter, offener Systeme ist nicht immer möglich. Obwohl ein offenes Systeme Funktionalität bereitstellt, die ein zweites offenes System benötigt, können Inkompatibilitäten in den Schnittstellen oder im Verhalten dazu führen, dass Nachrichten nicht korrekt ausgetauscht werden. Hier kommt die Idee eines Adapters zum Tragen, der solche Unterschiede ausgleicht. Wir führen eine Technik ein, die Inkompatibilitäten der Schnittstelle und des Verhaltens getrennt voneinander betrachtet. Mit Hilfe von Transformationsregeln geben wir an, wie Nachrichten zweier offener Systeme im Zusammenhang stehen. Wir modellieren so korrekten Datenfluss zwischen den Schnittstellen der offenen Systeme. Mit Hilfe existierender Techniken zur Controllersynthese erzeugen wir korrekten Kontrollfluss, sodass die Transformationsregeln so angewendet werden, dass Inkompatibilitäten im Verhalten überwunden werden. Wir erzeugen korrekten Kontrollfluss. Die Einheit aus Transformationsregeln und Controller bezeichnen wir als Adapter. Aufbauend auf dieser Technik betrachten wir in dieser Arbeit folgende Fragestellungen: - Welche Eigenschaften besitzt die vorgestellte Technik? Wann existiert ein Adapter? Wie lässt sich die Technik allgemein auf offene, kommunizierende Systeme anwenden? - Wie verteilen wir einen generierten Adapter auf verschiedene Komponenten? - Welche Informationen können wir bereitstellen, falls wir keinen Adapter finden? - Wie leiten wir ein formales Modell eines Adapters ab, wenn wir nur aufgezeichnetes Verhalten der offenen Systeme, aber keine formalen Modelle gegeben haben? / We consider open systems being described by an interface and behavior in form of an protocol. Interaction between open systems means exchange of messages. For the interaction to be correct, the interacting open systems must be able to terminate. The interaction of independently developed open systems is not guaranteed to be correct. Although one open system provides functionality a second open system requires, incompatiblities of the interfaces or the behavior may prevent the correct exchange of messages. The idea is to introduce an adapter to overcome the incompatiblities. We present a technique that considers incompatiblities of the interfaces and the behavior separately. With transformation rules we specify how messages of two open systems relate to each other. Using these rules we model the data flow between open systems and overcome incompatiblities of the interfaces. By using existing techniques for controller synthesis we overcome incompatiblities of the behavior. Thus we create correct control flow. We call the composition of transformation rules and controller an adapter. Based on the technique presented in this thesis, we want to answer the following reseach questions: - What are the properties of the proposed technique? When does an adapter exist? How can we apply the technique on open, communicating systems in general? - How do we distribute a generated adapter to different components? - Which information can we provide, if adapter synthesis fails? - How can we discover a formal model of an adapter, when we only have recorded behavior of open systems, but no formal models?

Die Auszeichnungssprache XML definiert eine einfache Syntax für strukturierte Daten, die sich so applikationsübergreifend einsetzen lassen. Eine der wichtigsten Voraussetzungen für den Austausch solcher XML-Daten ist die Möglichkeit ihrerTransformation. Unter den derzeit verfügbaren Transformationsmethoden für XML hat die Sprache XSLT als W3C-Standard die größte Verbreitung gefunden. Allerdings skaliert XSLT nicht für große Datenmengen, da hier eine Gesamtsicht auf das XML-Dokument vorausgesetzt wird. Andere existierende Transformationsmethoden besitzen entweder die gleiche Eigenschaft oder erfordern die Programmierung auf der XML-fernen Ebene einer Programmiersprache. In dieser Arbeit wird mit STX eine Transformationssprache für XML entwickelt, die diese Lücke füllt. STX orientiert sich sehr stark an XSLT, verarbeitet jedoch ein XML-Dokument als Datenstrom. STX kann so prinzipiell beliebig große Dokumente transformieren. Die aus der Sprache XPath 2.0 des W3C abgeleitete STX-Pfadsprache (STXPath) trägt dabei der eingeschränkten Sicht auf die zu transformierenden Daten Rechnung, indem sie nur den Zugriff auf die Vorfahren des jeweiligen Kontextknotens ermöglicht. Zu den neuartigen Konzepten in STX zählen neben prozeduralen Eigenschaften vor allem Gruppen, Schnittstellen zu externen Transformationsprozessen, die komplexe Transformation von Zeichenketten sowie Sprachmittel zur Fehlerbehandlung. Diese Arbeit stellt Entwurfsmuster für die wichtigsten Transformationstypen in STX vor und demonstriert an drei Fallbeispielen den Einsatz in realen Projekten. Der dazu verwendete STX-Prozessor Joost verfügt zudem über standardisierteJava-Schnittstellen, die dessen Integration in bestehende Java-Applikationen erleichtern. / The markup language XML defines a simple syntax for structured data that can be used across application boundaries. One of the most important prerequisites for the interchange of such XML data is the possibility of its transformation. Among the currently available transformation approaches for XML, the W3C standard XSLT has gained the biggest popularity. However, XSLT doesn''t scale for huge amounts of data because it requires an overall view to an XML document. Other existing transformation approaches either have the same character or require low-level programming using a general programming language. This PhD thesis introduces STX, an XML transformation language that fills this gap. STX is strongly geared to XSLT, though it processes an XML document as a stream. Therefore, STX is able to transform documents of any size. The STX path language (STXPath), derived from the W3C standard XPath 2.0, considers the restricted view to the input data and enables the access only to the ancestors of the current context node. The new concepts in STX include besides its procedural behaviour mainly groups, interfaces to external transformation processes, complex transformations of strings, as well as language means for error handling. This work introduces design patterns for the most important transformation types in STX and demonstrates three real-life scenarios. The STX processor Joost used for this purpose provides in addition standardized Java interfaces that facilitate its integration into existing Java applications.

Physikalische Simulation ist eine effektive und praktische Methode, um die Probleme der realen Welt zu untersuchen und zu erforschen. Jedoch kann die Simulation wertvolle Ergebnisse für die Robotik nur in enger Verbindung zu den realen Robotern liefern. In der Arbeit haben wie Methoden untersucht, die einen glatten Übergang von simulierten zu realen Robotern für die Steuerung humanoider Roboter erlauben. Wir haben ein Framework entwickelt, in dem Roboter sowohl in realen als auch in simulierten Umgebungen arbeiten können. Wir haben einen Simulator für humanoide Roboter auf konzeptioneller und experimenteller Ebene durch entsprechende Experimente evaluiert. Weiterhin haben wir den Simulator um zusätzliche Modelle erweitert und Parameter mithilfe Evolutionärer Algorithmen optimiert. Schließlich haben wir Bewegungen in Simulationen mit Maschinellem Lernen entwickelt und erfolgreich auf reale Roboter übertragen. Als Resultat können Roboter Teams sowohl in den Simulationsligen als auch in den realen Ligen des RoboCup mit identischen Steuerungen Fußball spielen. Das ergibt eine enge Verbindung zwischen den Entwicklern von simulierten und realen Robotern. / Physical simulation is an effective and practical method, to apply to the study and exploration of real world problems. However, simulation can offer valuable results for robotics only in close connection to real robots. In this thesis, we investigated how to create a mechanism that provides a smooth gradient to transfer humanoid robot control from simulated robot to real robot. We developed a framework for running robots both in real and simulated settings; and evaluated a humanoid robot simulator at a conceptual model level and results level by conducting experiments. Then, we improved the simulator by adding missing models and optimizing parameters with Evolutionary Algorithms. Finally, we developed motions in the simulations, with the help of Machine Learning, and transferred them to real robots successfully. As a result, a robot team can play soccer using identical controls in both the simulation and real RoboCup leagues. This constitutes a close connection between the communities working with simulated and real robots.

Fairneß (d.h. faire Konfliktlösung), Randomisierung (d.h. Münzwürfe) und partielle Synchronie sind verschiedene Konzepte, die häufig zur Lösung zentraler Synchronisations- und Koordinationsprobleme in verteilten Systemen verwendet werden. Beispiele für solche Probleme sind das Problem des wechselseitigen Ausschlusses (kurz: Mutex-Problem) sowie das Konsens-Problem. Für einige solcher Probleme wurde bewiesen, daß ohne die oben genannten Konzepte keine Lösung für das betrachtete Problem existiert. Unmöglichkeitsresultate dieser Art verbessern unser Verständnis der Wirkungsweise verteilter Algorithmen sowie das Verständnis des Trade-offs zwischen einem leicht analysierbaren und einem ausdrucksstarken Modell für verteiltes Rechnen. In dieser Arbeit stellen wir zwei neue Unmöglichkeitsresultate vor. Darüberhinaus beleuchten wir ihre Hintergründe. Wir betrachten dabei Modelle, die Randomisierung einbeziehen, da bisher wenig über die Grenzen der Ausdrucksstärke von Randomisierung bekannt ist. Mit einer Lösung eines Problems durch Randomisierung meinen wir, daß das betrachtete Problem mit Wahrscheinlichkeit 1 gelöst wird. Im ersten Teil der Arbeit untersuchen wir die Beziehung von Fairneß und Randomisierung. Einerseits ist bekannt, daß einige Probleme (z.B. das Konsens- Problem) durch Randomisierung nicht aber durch Fairneß lösbar sind. Wir zeigen nun, daß es andererseits auch Probleme gibt (nämlich das Mutex-Problem), die durch Fairneß, nicht aber durch Randomisierung lösbar sind. Daraus folgt, daß Fairneß nicht durch Randomisierung implementiert werden kann. Im zweiten Teil der Arbeit verwenden wir ein Modell, das Fairneß und Randomisierung vereint. Ein solches Modell ist relativ ausdrucksstark: Es erlaubt Lösungen für das Mutex-Problem, das Konsens-Problem, sowie eine Lösung für das allgemeine Mutex-Problem. Beim allgemeinen Mutex-Problem (auch bekannt als Problem der speisenden Philosophen) ist eine Nachbarschaftsrelation auf den Agenten gegeben und ein Algorithmus gesucht, der das Mutex-Problem für jedes Paar von Nachbarn simultan löst. Schließlich betrachten wir das ausfalltolerante allgemeine Mutex-Problem -- eine Variante des allgemeinen Mutex-Problems, bei der Agenten ausfallen können. Wir zeigen, daß sogar die Verbindung von Fairneß und Randomisierung nicht genügt, um eine Lösung für das ausfalltolerante allgemeine Mutex-Problem zu konstruieren. Ein Hintergrund für dieses Unmöglichkeitsresultat ist ein unerwünschtes Phänomen, für das in der Literatur der Begriff Konspiration geprägt wurde. Konspiration wurde bisher nicht adäquat charakterisiert. Wir charakterisieren Konspiration auf der Grundlage nicht-sequentieller Abläufe. Desweiteren zeigen wir, daß Konspiration für eine große Klasse von Systemen durch die zusätzliche Annahme von partieller Synchronie verhindert werden kann, d.h. ein konspirationsbehaftetes System kann zu einem randomisierten System verfeinert werden, das unter Fairneß und partieller Synchronie mit Wahrscheinlichkeit 1 konspirationsfrei ist. Partielle Synchronie fordert, daß alle relativen Geschwindigkeiten im System durch eine Konstante beschränkt sind, die jedoch den Agenten nicht bekannt ist. Die Darstellung der Unmöglichkeitsresultate und die Charakterisierung von Konspiration wird erst durch die Verwendung nicht-sequentieller Abläufe möglich. Ein nicht-sequentieller Ablauf repräsentiert im Gegensatz zu einem sequentiellen Ablauf kausale Ordnung und nicht zeitliche Ordnung von Ereignissen. Wir entwickeln in dieser Arbeit eine nicht-sequentielle Semantik für randomisierte verteilte Algorithmen, da es bisher keine in der Literatur gibt. In dieser Semantik wird kausale Unabhängigkeit durch stochastische Unabhängigkeit widergespiegelt. / Concepts such as fairness (i.e., fair conflict resolution), randomization (i.e., coin flips), and partial synchrony are frequently used to solve fundamental synchronization- and coordination-problems in distributed systems such as the mutual exclusion problem (mutex problem for short) and the consensus problem. For some problems it is proven that, without such concepts, no solution to the particular problem exists. Impossibilty results of that kind improve our understanding of the way distributed algorithms work. They also improve our understanding of the trade-off between a tractable model and a powerful model of distributed computation. In this thesis, we prove two new impossibility results and we investigate their reasons. We are in particular concerned with models for randomized distributed algorithms since little is yet known about the limitations of randomization with respect to the solvability of problems in distributed systems. By a solution through randomization we mean that the problem under consideration is solved with probability 1. In the first part of the thesis, we investigate the relationship between fairness and randomization. On the one hand, it is known that to some problems (e.g. to the consensus problem), randomization admits a solution where fairness does not admit a solution. On the other hand, we show that there are problems (viz. the mutex problem) to which randomization does not admit a solution where fairness does admit a solution. These results imply that fairness cannot be implemented by coin flips. In the second part of the thesis, we consider a model which combines fairness and randomization. Such a model is quite powerful, allowing solutions to the mutex problem, the consensus problem, and a solution to the generalized mutex problem. In the generalized mutex problem (a.k.a. the dining philosophers problem), a neighborhood relation is given and mutual exclusion must be achieved for each pair of neighbors. We finally consider the crash-tolerant generalized mutex problem where every hungry agent eventually becomes critical provided that neither itself nor one of its neighbors crashes. We prove that even the combination of fairness and randomization does not admit a solution to the crash-tolerant generalized mutex problem. We argue that the reason for this impossibility is the inherent occurrence of an undesirable phenomenon known as conspiracy. Conspiracy was not yet properly characterized. We characterize conspiracy on the basis of non-sequential runs, and we show that conspiracy can be prevented by help of the additional assumption of partial synchrony, i.e., we show that every conspiracy-prone system can be refined to a randomized system which is, with probability 1, conspiracy-free under the assumptions of partial synchrony and fairness. Partial synchrony means that each event consumes a bounded amount of time where, however, the bound is not known. We use a non-sequential semantics for distributed algorithms which is essential to some parts of the thesis. In particular, we develop a non-sequential semantics for randomized distributed algorithms since there is no such semantics in the literature. In this non-sequential semantics, causal independence is reflected by stochastic independence.

In der Ramsey Theorie fuer Graphen haben Burr und Erdos vor nunmehr fast dreissig Jahren zwei Vermutungen formuliert, die sich als richtungsweisend erwiesen haben. Es geht darum diejenigen Graphen zu charakterisieren, deren Ramsey Zahlen linear in der Anzahl der Knoten wachsen. Diese Vermutungen besagen, dass Ramsey Zahlen linear fuer alle degenerierten Graphen wachsen und dass die Ramsey Zahlen von Wuerfeln linear wachsen. Ein Ziel dieser Dissertation ist es, abgeschwaechte Varianten dieser Vermutungen zu beweisen. In der topologischen Ramseytheorie bewies Kojman vor kurzem eine topologische Umkehrung des Satzes von Hindman und fuehrte gleichzeitig sogenannte Hindman-Raeume und van der Waerden-Raeume ein (beide sind eine Teilmenge der folgenkompakten Raeume), die jeweils zum Satz von Hindman beziehungsweise zum Satz von van der Waerden korrespondieren. In der Dissertation wird zum einen eine Verstaerkung der Umkehrung des Satzes von van der Waerden bewiesen. Weiterhin wird der Begriff der Differentialkompaktheit eingefuehrt, der sich in diesem Zusammenhang ergibt und der eng mit Hindman-Raeumen verknuepft ist. Dabei wird auch die Beziehung zwischen Differentialkompaktheit und anderen topologischen Raeumen untersucht. Im letzten Abschnitt des zweiten Teils werden kompakte dynamische Systeme verwendet, um ein klassisches Ramsey-Ergebnis von Brown und Hindman et al. ueber stueckweise syndetische Mengen ueber natuerlichen Zahlen und diskreten Halbgruppen auf lokal zusammenhaengende Halbgruppen zu verallgemeinern. / In graph Ramsey theory, Burr and Erdos in 1970s posed two conjectures which may be considered as initial steps toward the problem of characterizing the set of graphs for which Ramsey numbers grow linearly in their orders. One conjecture is that Ramsey numbers grow linearly for all degenerate graphs and the other is that Ramsey numbers grow linearly for cubes. Though unable to settle these two conjectures, we have contributed many weaker versions that support the likely truth of the first conjecture and obtained a polynomial upper bound for the Ramsey numbers of cubes that considerably improves all previous bounds and comes close to the linear bound in the second conjecture. In topological Ramsey theory, Kojman recently observed a topological converse of Hindman's theorem and then introduced the so-called Hindman space and van der Waerden space (both of which are stronger than sequentially compact spaces) corresponding respectively to Hindman's theorem and van der Waerden's theorem. In this thesis, we will strengthen the topological converse of Hindman's theorem by using canonical Ramsey theorem, and introduce differential compactness that arises naturally in this context and study its relations to other spaces as well. Also by using compact dynamical systems, we will extend a classical Ramsey type theorem of Brown and Hindman et al on piecewise syndetic sets from natural numbers and discrete semigroups to locally connected semigroups.