Many complexity measures are defined as the size of a minimal representation in a specific model class. One such complexity measure, which is important because it is widely applied, is statistical complexity. It is defined for discrete-time, stationary stochastic processes within a theory called computational mechanics. Here, a mathematically rigorous, more general version of this theory is presented, and abstract properties of statistical complexity as a function on the space of processes are investigated. In particular, weak-* lower semi-continuity and concavity are shown, and it is argued that these properties should be shared by all sensible complexity measures. Furthermore, a formula for the ergodic decomposition is obtained. The same results are also proven for two other complexity measures that are defined by different model classes, namely process dimension and generative complexity. These two quantities, and also the information theoretic complexity measure called excess entropy, are related to statistical complexity, and this relation is discussed here. It is also shown that computational mechanics can be reformulated in terms of Frank Knight's prediction process, which is of both conceptual and technical interest. In particular, it allows for a unified treatment of different processes and facilitates topological considerations. Continuity of the Markov transition kernel of a discrete version of the prediction process is obtained as a new result.

Assessment of odor thresholds is a widely recognized method of measuring olfactory abilities in humans. To date no attempts have been made to assess whether chemical complexity of odors used can produce more reliable results. To this end, we performed two studies of repeated measures design with 121 healthy volunteers (age 19–62 years). In Study 1, we compared thresholds obtained from tests based on one odor presented in a pen-like odor dispensing device with three odors and six odors mixtures presented in glass containers. In study 2 we compared stimuli of one and three odors, both presented in glass containers. In both studies measurements were performed twice, separated by at least three days. Results indicate that the multiple odor mixtures produced more reliable threshold scores, as compared to thresholds based on a single substance.

In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.

In large and complex systems, failures can have dramatic consequences, such as black-outs, pandemics or the loss of entire classes of an ecosystem. Nevertheless, it is a centuries-old intuition that by using networks to capture the core of the complexity of such systems, one might understand in which part of a system a phenomenon originates. I investigate this intuition using spectral methods to decouple the dynamics of complex systems near stationary states into independent dynamical modes. In this description, phenomena are tied to a specific part of a system through localized eigenvectors which have large amplitudes only on a few nodes of the system's network. Studying the occurrence of localized eigenvectors, I find that such localization occurs exactly for a few small network structures, and approximately for the dynamical modes associated with the most prominent failures in complex systems. My findings confirm that understanding the functioning of complex systems generally requires to treat them as complex entities, rather than collections of interwoven small parts. Exceptions to this are only few structures carrying exact localization, whose functioning is tied to the meso-scale, between the size of individual elements and the size of the global network. However, while understanding the functioning of a complex system is hampered by the necessary global analysis, the prominent failures, due to their localization, allow an understanding on a manageable local scale. Intriguingly, food webs might exploit this localization of failures to stabilize by causing the break-off of small problematic parts, whereas typical attempts to optimize technological systems for stability lead to delocalization and large-scale failures. Thus, this thesis provides insights into the interplay of complexity and localization, which is paramount to ascertain the functioning of the ever-growing networks on which we humans depend.:1 Introduction 2 Concepts and Tools 2.1 Networks 2.2 Food webs 2.3 Dynamics on networks 2.4 Steady state operating modes 2.5 Bifurcations affecting operating modes 2.6 Dynamical modes 2.7 Generalized models for food webs 3 Perturbation Impact 3.1 Impact of perturbations on food webs 3.2 Examples 3.3 Impact formulation with dynamical modes 3.4 Influence and sensitivity of species 3.5 Localized dynamical modes 3.6 Iterative parameter estimation 3.7 Most important parameters and species 3.8 Discussion 4 Exact Localization 4.1 Graph symmetries 4.2 Localized dynamics on symmetries 4.3 Exactly localized dynamics 4.4 Symmetry reduction in networks 4.5 Application to food webs 4.6 Localization on asymmetric structures 4.7 Nearly-exact localization 4.8 Other systems 4.9 Discussion 5 Approximate Localization 5.1 Spread of a dynamical mode 5.2 Examples for localized instabilities 5.3 Localization of extreme eigenvalues 5.4 Dependence on the system size 5.5 Localization in the model of R. May 5.6 Finding motifs that carry localization 5.7 (Self-)stabilization of food webs 5.8 Repairing localized instabilities 5.9 Discussion 6 Conclusions Acknowledgments Appendix A Parametrization of the Gatun Lake food web B The Master Stability Function approach C Approximate localization on larger structures Bibliography

This thesis describes the development and setup of hybrid index structures. They are access methods for retrieval techniques in hybrid data spaces which are formed by one or more relational or normalised columns in conjunction with one non-relational or non-normalised column. Examples for these hybrid data spaces are, among others, textual data combined with geographical ones or data from enterprise content management systems. However, all non-relational data types may be stored as well as image feature vectors or comparable types. Hybrid index structures are known to function efficiently regarding retrieval operations. Unfortunately, little information is available about reorganisation operations which insert or update the row tuples. The fundamental research is mainly executed in simulation based environments. This work is written ensuing from a previous thesis that implements hybrid access structures in realistic database surroundings. During this implementation it has become obvious that retrieval works efficiently. Yet, the restructuring approaches require too much effort to be set up, e.g., in web search engine environments where several thousands of documents are inserted or modified every day. These search engines rely on relational database systems as storage backends. Hence, the setup of these access methods for hybrid data spaces is required in real world database management systems. This thesis tries to apply a systematic approach for the optimisation of the rearrangement algorithms inside realistic scenarios. Thus, a measurement and evaluation scheme is created which is repeatedly deployed to an evolving state and a model of hybrid index structures in order to optimise the regrouping algorithms to make a setup of hybrid index structures in real world information systems possible. Thus, a set of input corpora is selected which is applied to the test suite as well as an evaluation scheme. To sum up, it can be said that this thesis describes input sets, a test suite including an evaluation scheme as well as optimisation iterations on reorganisation algorithms reflecting a theoretical model framework to provide efficient reorganisations of hybrid index structures supporting multimedia search criteria.

Many complexity measures are defined as the size of a minimal representation in a specific model class. One such complexity measure, which is important because it is widely applied, is statistical complexity. It is defined for discrete-time, stationary stochastic processes within a theory called computational mechanics. Here, a mathematically rigorous, more general version of this theory is presented, and abstract properties of statistical complexity as a function on the space of processes are investigated. In particular, weak-* lower semi-continuity and concavity are shown, and it is argued that these properties should be shared by all sensible complexity measures. Furthermore, a formula for the ergodic decomposition is obtained. The same results are also proven for two other complexity measures that are defined by different model classes, namely process dimension and generative complexity. These two quantities, and also the information theoretic complexity measure called excess entropy, are related to statistical complexity, and this relation is discussed here. It is also shown that computational mechanics can be reformulated in terms of Frank Knight''s prediction process, which is of both conceptual and technical interest. In particular, it allows for a unified treatment of different processes and facilitates topological considerations. Continuity of the Markov transition kernel of a discrete version of the prediction process is obtained as a new result.

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack, while the follower chooses a feasible packing maximizing his own profit. The leader’s aim is to optimize a linear objective function in the capacity and in the follower’s solution, but with respect to different item values. We address a stochastic version of this problem where the follower’s profits are uncertain from the leader’s perspective, and only a probability distribution is known. Assuming that the leader aims at optimizing the expected value of her objective function, we first observe that the stochastic problem is tractable as long as the possible scenarios are given explicitly as part of the input,which also allows to deal with general distributions using a sample average approximation. For the case of independently and uniformly distributed item values, we show that the problem is #P-hard in general, and the same is true even for evaluating the leader’s objective function. Nevertheless, we present pseudo-polynomial time algorithms for this case, running in time linear in the total size of the items.Based on this,we derive an additive approximation scheme for the general case of independently distributed item values, which runs in pseudo-polynomial time.

Diese Arbeit leistet Beiträge im Bereich der deskriptiven Komplexitätstheorie. Zunächst beschäftigen wir uns mit der ungelösten Frage, ob es eine Logik gibt, welche die Klasse der Polynomialzeit-Eigenschaften (PTIME) charakterisiert. Wir betrachten Graphklassen, die unter induzierten Teilgraphen abgeschlossen sind. Auf solchen Graphklassen lässt sich die 1976 von Gallai eingeführte modulare Zerlegung anwenden. Graphen, die durch modulare Zerlegung nicht zerlegbar sind, heißen prim. Wir stellen ein neues Werkzeug vor: das Modulare Zerlegungstheorem. Es reduziert (definierbare) Kanonisierung einer Graphklasse C auf (definierbare) Kanonisierung der Klasse aller primen Graphen aus C, die mit binären Relationen auf einer linear geordneten Menge gefärbt sind. Mit Hilfe des Modularen Zerlegungstheorems zeigen wir, dass Fixpunktlogik mit Zählen (FP+C) PTIME auf der Klasse aller Permutationsgraphen und auf der Klasse aller chordalen Komparabilitätsgraphen charakterisiert. Wir beweisen zudem, dass modulare Zerlegungsbäume in Symmetrisch-Transitive-Hüllen-Logik mit Zählen (STC+C) definierbar und damit in logarithmischem Platz berechenbar sind. Weiterhin definieren wir eine neue Logik für die Komplexitätsklasse Logarithmischer Platz (LOGSPACE). Wir erweitern die Logik erster Stufe mit Zählen um einen Operator, der eine in logarithmischem Platz berechenbare Form der Rekursion erlaubt. Die resultierende Logik LREC ist ausdrucksstärker als die Deterministisch-Transitive-Hüllen-Logik mit Zählen (DTC+C) und echt in FP+C enthalten. Wir zeigen, dass LREC LOGSPACE auf gerichteten Bäumen charakterisiert. Zudem betrachten wir eine Erweiterung LREC= von LREC, die sich gegenüber LREC durch bessere Abschlusseigenschaften auszeichnet und im Gegensatz zu LREC ausdrucksstärker als die Symmetrisch-Transitive-Hüllen-Logik (STC) ist. Wir beweisen, dass LREC= LOGSPACE sowohl auf der Klasse der Intervallgraphen als auch auf der Klasse der chordalen klauenfreien Graphen charakterisiert. / This theses is making contributions to the field of descriptive complexity theory. First, we look at the main open problem in this area: the question of whether there exists a logic that captures polynomial time (PTIME). We consider classes of graphs that are closed under taking induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed-point logic with counting (FP+C) captures PTIME on the class of permutation graphs and the class of chordal comparability graphs. We also prove that the modular decomposition tree is definable in symmetric transitive closure logic with counting (STC+C), and therefore, computable in logarithmic space. Further, we introduce a new logic for the complexity class logarithmic space (LOGSPACE). We extend first-order logic with counting by a new operator that allows it to formalize a limited form of recursion which can be evaluated in logarithmic space. We prove that the resulting logic LREC is strictly more expressive than deterministic transitive closure logic with counting (DTC+C) and that it is strictly contained in FP+C. We show that LREC captures LOGSPACE on the class of directed trees. We also study an extension LREC= of LREC that has nicer closure properties and that, unlike LREC, is more expressive than symmetric transitive closure logic (STC). We prove that LREC= captures LOGSPACE on the class of interval graphs and on the class of chordal claw-free graphs.

Wird der Äquator-Pol-Energietransfer als Wärmediffusion berücksichtigt, so gehen Energiebilanzmodelle in Reaktions-Diffusionsgleichungen über, deren Modellfall die (deterministische) Chafee-Infante-Gleichung darstellt. Ihre Lösung besitzt zwei stabile Zustände und mehrere instabile auf der separierenden Mannigfaltigkeit (Separatrix) der stabilen Anziehungsgebiete. Es wird bewiesen, dass die Lösung auf geeignet verkleinerten Anziehungsgebieten mit Minimalabstand zur Separatrix innerhalb von Zeitskalen relaxiert, die höchstens logarithmisch darin anwachsen. Motiviert durch statistische Belege aus grönländischen Zeitreihen wird diese partielle Differentialgleichung unter Störung mit unendlichdimensionalem, Hilbertraum-wertigen, regulär variierenden Lévy''schen reinen Sprungrauschen mit index alpha und Intensität epsilon untersucht. Ein kanonisches Beispiel dieses Rauschens ist alpha-stabiles Rauschen im Hilbertraum. Durch Erweiterung einer Methode von Imkeller und Pavlyukevich auf stochastische partielle Differentialgleichungen wird unter milden Bedingungen bewiesen, dass im Gegensatz zu Gauß''schem Rauschen die erwarteten Austritts- und übertrittszeiten zwischen Anziehungsgebieten polynomiell mit Ordnung in der inversen Intensität für kleine Rauschintensität anwachsen. In Kapitel 6 wird eine zusätzliche natürliche “Separatrixhypothese” über das Sprungmaß, eingeführt, die eine obere Schranke für die Austrittszeiten aus einer Umgebung der Separatrix impliziert. Dies ermöglicht den Nachweis einer oberen Schranke für die Austrittszeiten, welche gleichmäßig für Anfangsbedingungen in dem ganzen Anziehungsgebiet gilt. Es folgen zwei Lokalisierungsergebnisse. Schließlich wird gezeigt, dass die Lösung metastabiles Verhalten aufweist. Unter der “Separatrixhypothese” wird dies auf ein Ergebnis erweitert, welches gleichmäßig im Raum gilt. / If equator-to-pole energy transfer by heat diffusion is taken into account, Energy Balance Models turn into reaction-diffusion equations, whose prototype is the (deterministic) Chafee-Infante equation. Its solution has two stable states and several unstable ones on the separating manifold (separatrix) of the stable domains of attraction. We show, that on appropriately reduced domains of attraction of a minimal distance to the separatrix the solution relaxes in time scales increasing only logarithmically in it. Motivated by the statistical evidence from Greenland ice core time series, we consider this partial differential equation perturbed by an infinite-dimensional Hilbert space-valued regularly varying (pure jump) Lévy noise of index alpha and intensity epsilon. A proto-type of this noise is alpha-stable noise in the Hilbert space. Extending a method developed by Imkeller and Pavlyukevich to the SPDE setting we prove under mild conditions that in contrast to Gaussian perturbations the expected exit and transition times between the domains of attraction increase polynomially in the inverse intensity. In Chapter 6 we introduce an additional natural separatrix hypothesis on the jump measure that implies an upper bound on the exit time of a neighborhood of the separatrix. This allows to obtain an upper bound for the asymptotic exit time uniform for the initial positions inside the entire domain of attraction. It is followed by two localization results. Finally we prove that the solution exhibits metastable behavior. Under the separatrix hypothesis we can extend this to a result that holds uniformly in space.

Zahlungen für Ökosystemdienstleistungen (Payments for EcosystemServices, PES) sind in den letzten Jahren zum Aushängeschild von Umweltorganisation geworden. Der Gedanke, die Bereitstellung von Ökosystemdienstleistungen durch PES abzusichern, ist in praktischen Diskursen von Vermittlern zu finden, die an potentiell Zahlende gerichtet sind. Praktikern ist bisher jedoch schwer gefallen, zu zeigen, dass PES tatsächlich zu den vorgesehenen Zielen führen können. Forscher haben darauf hingewiesen, dass zahlreiche PES-Schemata, insbesondere diejenigen mit Bezug auf Wasser, auf unsicheren Annahmen beruhen und außerdem gewichtige Kausalzusammenhänge zwischen Eingriffen in die Landnutzung und Ökosystemdienstleistungen vermissen lassen. Diese Unsicherheit in PES-Schemata geht nicht nur aus praktischen Schwierigkeiten hervor, sondern aus der Komplexität von Mensch-Umwelt-Systemen (human-environment systems) und aus der Begrenztheit des Wissens über diese Systeme. Forscher sind zwar in derLage, diese wesentlichen Herausforderungen zu beschreiben und zu diskutieren. In der Fachliteratur mangelt es jedoch an empirischen Studien,die die zusätzliche Wirksamkeitvon PES-Schemata untersuchen, d.h. ob diese Schemata zusätzliche Wirkungen zeigen, die anderen Faktoren nicht zurechenbar sind, bzw. Studien, die die Bedeutung von Nachweisen für ihre Wirksamkeit für die Interessengruppen (stakeholders) untersuchen. Die Dissertation trägt dazu bei, diese empirische Lücke zu schließen: Dazu untersucht sie vier wasserbezogene Zahlungsschemata, hier auch Zahlungen für Wassereinzugsgebietsleistungen genannt, in Kolumbien. Sie vergleicht die vier Fälle hinsichtlich der Bestrebungen, durch Beobachtung (monitoring) und Evaluation Nachweise für die Wirksamkeit zu erbringen, sowie hinsichtlich der damit verbundenen Herausforderungen. Eines der Kapitel enthält auch drei Fallstudien aus Brasilien, die als Vergleich zu den Fällen aus Kolumbien und der Darstellung von Unterschieden und Gemeinsamkeiten dienen. / Payments for Ecosystem Services (PES) have become the flagship of conservation organizations in recent years. The idea of securing ecosystem service (ES) provision through PES has been present in practical discourses of intermediaries directed at potential payers. However, demonstrating that PES can actually achieve the intended goals has been difficult for practitioners. Researchers have pointed out that many PES schemes, particularly water-related ones, are based on unreliable assumptions and lack strong causal links between land use interventions and ecosystem services. This uncertainty in PES schemes arises not only from practical difficulties, but from the complexity of human-environment systems (HES), and the limits of knowledge about them. Researchers have been able to describe and discuss these major challenges. However, the literature is still poor on empirical studies exploring the additionality of PES schemes, that is, if those schemes produce additional effects not attributable to other factors, as well as studies exploring the importance of impact evidence for stakeholders involved. This dissertation contributes to filling this empirical gap by exploring four water-related payments schemes (here also called payments for watershed services, PWS) in Colombia, comparing the cases in terms of their efforts to produce impact evidence through monitoring and evaluation, and their associated challenges. Three cases from Brazil are also included in one of the chapters and compared with the Colombian cases by illustrating differences and similarities.