By counting 1's in the "right half" of 2w consecutive rows, we locate the main diagonal of any doubly infinite permutation matrix with bandwidth w. Then the matrix can be correctly centered and factored into block-diagonal permutation matrices. Part II of the paper discusses the same questions for the much larger class of band-dominated matrices. The main diagonal is determined by the Fredholm index of a singly infinite submatrix. Thus the main diagonal is determined "at infinity" in general, but from only 2w rows for banded permutations.

By counting 1's in the "right half" of 2w consecutive rows, we locate the main diagonal of any doubly infinite permutation matrix with bandwidth w. Then the matrix can be correctly centered and factored into block-diagonal permutation matrices. Part II of the paper discusses the same questions for the much larger class of band-dominated matrices. The main diagonal is determined by the Fredholm index of a singly infinite submatrix. Thus the main diagonal is determined "at infinity" in general, but from only 2w rows for banded permutations.

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.

This work is concerned with the characterization of certain classes of stochastic processes via duality formulae. In particular we consider reciprocal processes with jumps, a subject up to now neglected in the literature. In the first part we introduce a new formulation of a characterization of processes with independent increments. This characterization is based on a duality formula satisfied by processes with infinitely divisible increments, in particular Lévy processes, which is well known in Malliavin calculus. We obtain two new methods to prove this duality formula, which are not based on the chaos decomposition of the space of square-integrable function- als. One of these methods uses a formula of partial integration that characterizes infinitely divisible random vectors. In this context, our characterization is a generalization of Stein’s lemma for Gaussian random variables and Chen’s lemma for Poisson random variables. The generality of our approach permits us to derive a characterization of infinitely divisible random measures. The second part of this work focuses on the study of the reciprocal classes of Markov processes with and without jumps and their characterization. We start with a resume of already existing results concerning the reciprocal classes of Brownian diffusions as solutions of duality formulae. As a new contribution, we show that the duality formula satisfied by elements of the reciprocal class of a Brownian diffusion has a physical interpretation as a stochastic Newton equation of motion. Thus we are able to connect the results of characterizations via duality formulae with the theory of stochastic mechanics by our interpretation, and to stochastic optimal control theory by the mathematical approach. As an application we are able to prove an invariance property of the reciprocal class of a Brownian diffusion under time reversal. In the context of pure jump processes we derive the following new results. We describe the reciprocal classes of Markov counting processes, also called unit jump processes, and obtain a characterization of the associated reciprocal class via a duality formula. This formula contains as key terms a stochastic derivative, a compensated stochastic integral and an invariant of the reciprocal class. Moreover we present an interpretation of the characterization of a reciprocal class in the context of stochastic optimal control of unit jump processes. As a further application we show that the reciprocal class of a Markov counting process has an invariance property under time reversal. Some of these results are extendable to the setting of pure jump processes, that is, we admit different jump-sizes. In particular, we show that the reciprocal classes of Markov jump processes can be compared using reciprocal invariants. A characterization of the reciprocal class of compound Poisson processes via a duality formula is possible under the assumption that the jump-sizes of the process are incommensurable. / Diese Arbeit befasst sich mit der Charakterisierung von Klassen stochastischer Prozesse durch Dualitätsformeln. Es wird insbesondere der in der Literatur bisher unbehandelte Fall reziproker Klassen stochastischer Prozesse mit Sprungen untersucht. Im ersten Teil stellen wir eine neue Formulierung einer Charakterisierung von Prozessen mit unabhängigen Zuwächsen vor. Diese basiert auf der aus dem Malliavinkalkül bekannten Dualitätsformel für Prozesse mit unendlich oft teilbaren Zuwächsen. Wir präsentieren zusätzlich zwei neue Beweismethoden dieser Dualitätsformel, die nicht auf der Chaoszerlegung des Raumes quadratintegrabler Funktionale beruhen. Eine dieser Methoden basiert auf einer partiellen Integrationsformel fur unendlich oft teilbare Zufallsvektoren. In diesem Rahmen ist unsere Charakterisierung eine Verallgemeinerung des Lemma fur Gaußsche Zufallsvariablen von Stein und des Lemma fur Zufallsvariablen mit Poissonverteilung von Chen. Die Allgemeinheit dieser Methode erlaubt uns durch einen ähnlichen Zugang die Charakterisierung unendlich oft teilbarer Zufallsmaße. Im zweiten Teil der Arbeit konzentrieren wir uns auf die Charakterisierung reziproker Klassen ausgewählter Markovprozesse durch Dualitätsformeln. Wir beginnen mit einer Zusammenfassung bereits existierender Ergebnisse zu den reziproken Klassen Brownscher Bewegungen mit Drift. Es ist uns möglich die Charakterisierung solcher reziproken Klassen durch eine Dualitätsformel physikalisch umzudeuten in eine Newtonsche Gleichung. Damit gelingt uns ein Brückenschlag zwischen derartigen Charakterisierungsergebnissen und der Theorie stochastischer Mechanik durch den Interpretationsansatz, sowie der Theorie stochastischer optimaler Steuerung durch den mathematischen Ansatz. Unter Verwendung der Charakterisierung reziproker Klassen durch Dualitätsformeln beweisen wir weiterhin eine Invarianzeigenschaft der reziproken Klasse Browscher Bewegungen mit Drift unter Zeitumkehrung. Es gelingt uns weiterhin neue Resultate im Rahmen reiner Sprungprozesse zu beweisen. Wir beschreiben reziproke Klassen Markovscher Zählprozesse, d.h. Sprungprozesse mit Sprunghöhe eins, und erhalten eine Charakterisierung der reziproken Klasse vermöge einer Dualitätsformel. Diese beinhaltet als Schlüsselterme eine stochastische Ableitung nach den Sprungzeiten, ein kompensiertes stochastisches Integral und eine Invariante der reziproken Klasse. Wir präsentieren außerdem eine Interpretation der Charakterisierung einer reziproken Klasse im Rahmen der stochastischen Steuerungstheorie. Als weitere Anwendung beweisen wir eine Invarianzeigenschaft der reziproken Klasse Markovscher Zählprozesse unter Zeitumkehrung. Einige dieser Ergebnisse werden fur reine Sprungprozesse mit unterschiedlichen Sprunghöhen verallgemeinert. Insbesondere zeigen wir, dass die reziproken Klassen Markovscher Sprungprozesse vermöge reziproker Invarianten unterschieden werden können. Eine Charakterisierung der reziproken Klasse zusammengesetzter Poissonprozesse durch eine Dualitätsformel gelingt unter der Annahme inkommensurabler Sprunghöhen.

No description available.

This thesis is concerned with automata over infinite trees. They are given a labeled infinite tree and accept or reject this tree based on its labels. A generalization of these automata with binary decisions are weighted automata. They do not just decide 'yes' or 'no', but rather compute an arbitrary value from a given algebraic structure, e.g., a semiring or a lattice. When passing from unweighted to weighted formalisms, many problems can be translated accordingly. The purpose of this work is to determine the feasibility of solving the inclusion problem for automata on infinite trees and its generalization to weighted automata, the infimum aggregation problem.

Diese Examensarbeit untersucht die Verbindung zwischen Die unendliche Geschichte von Michael Ende und der deutschen Epoche Romantik. Dies wird anhand einer textimmanenten Analyse von Die unendliche Geschichte und E.T.A Hoffmanns romantisches Werk Der goldne Topf durchgeführt.

Corvino, Corvino and Schoen, Chruściel and Delay have shown the existence of a large class of asymptotically flat vacuum initial data for Einstein's field equations which are static or stationary in a neighborhood of space-like infinity, yet quite general in the interior. The proof relies on some abstract, non-constructive arguments which makes it difficult to calculate such data numerically by using similar arguments. A quasilinear elliptic system of equations is presented of which we expect that it can be used to construct vacuum initial data which are asymptotically flat, time-reflection symmetric, and asymptotic to static data up to a prescribed order at space-like infinity. A perturbation argument is used to show the existence of solutions. It is valid when the order at which the solutions approach staticity is restricted to a certain range. Difficulties appear when trying to improve this result to show the existence of solutions that are asymptotically static at higher order. The problems arise from the lack of surjectivity of a certain operator. Some tensor decompositions in asymptotically flat manifolds exhibit some of the difficulties encountered above. The Helmholtz decomposition, which plays a role in the preparation of initial data for the Maxwell equations, is discussed as a model problem. A method to circumvent the difficulties that arise when fast decay rates are required is discussed. This is done in a way that opens the possibility to perform numerical computations. The insights from the analysis of the Helmholtz decomposition are applied to the York decomposition, which is related to that part of the quasilinear system which gives rise to the difficulties. For this decomposition analogous results are obtained. It turns out, however, that in this case the presence of symmetries of the underlying metric leads to certain complications. The question, whether the results obtained so far can be used again to show by a perturbation argument the existence of vacuum initial data which approach static solutions at infinity at any given order, thus remains open. The answer requires further analysis and perhaps new methods. / Corvino, Corvino und Schoen als auch Chruściel und Delay haben die Existenz einer grossen Klasse asymptotisch flacher Anfangsdaten für Einsteins Vakuumfeldgleichungen gezeigt, die in einer Umgebung des raumartig Unendlichen statisch oder stationär aber im Inneren der Anfangshyperfläche sehr allgemein sind. Der Beweis beruht zum Teil auf abstrakten, nicht konstruktiven Argumenten, die Schwierigkeiten bereiten, wenn derartige Daten numerisch berechnet werden sollen. In der Arbeit wird ein quasilineares elliptisches Gleichungssystem vorgestellt, von dem wir annehmen, dass es geeignet ist, asymptotisch flache Vakuumanfangsdaten zu berechnen, die zeitreflektionssymmetrisch sind und im raumartig Unendlichen in einer vorgeschriebenen Ordnung asymptotisch zu statischen Daten sind. Mit einem Störungsargument wird ein Existenzsatz bewiesen, der gilt, solange die Ordnung, in welcher die Lösungen asymptotisch statische Lösungen approximieren, in einem gewissen eingeschränkten Bereich liegt. Versucht man, den Gültigkeitsbereich des Satzes zu erweitern, treten Schwierigkeiten auf. Diese hängen damit zusammen, dass ein gewisser Operator nicht mehr surjektiv ist. In einigen Tensorzerlegungen auf asymptotisch flachen Räumen treten ähnliche Probleme auf, wie die oben erwähnten. Die Helmholtzzerlegung, die bei der Bereitstellung von Anfangsdaten für die Maxwellgleichungen eine Rolle spielt, wird als ein Modellfall diskutiert. Es wird eine Methode angegeben, die es erlaubt, die Schwierigkeiten zu umgehen, die auftreten, wenn ein schnelles Abfallverhalten des gesuchten Vektorfeldes im raumartig Unendlichen gefordert wird. Diese Methode gestattet es, solche Felder auch numerisch zu berechnen. Die Einsichten aus der Analyse der Helmholtzzerlegung werden dann auf die Yorkzerlegung angewandt, die in den Teil des quasilinearen Systems eingeht, der Anlass zu den genannten Schwierigkeiten gibt. Für diese Zerlegung ergeben sich analoge Resultate. Es treten allerdings Schwierigkeiten auf, wenn die zu Grunde liegende Metrik Symmetrien aufweist. Die Frage, ob die Ergebnisse, die soweit erhalten wurden, in einem Störungsargument verwendet werden können um die Existenz von Vakuumdaten zu zeigen, die im räumlich Unendlichen in jeder Ordnung statische Daten approximieren, bleibt daher offen. Die Antwort erfordert eine weitergehende Untersuchung und möglicherweise auch neue Methoden.

Diese Arbeit analysiert, aus einer literatursoziologischen Perspektive, wie die vier ausgewählten Romane die Gesellschaft kritisieren. Man kann Gesellschaftskritik in allen diesen Romanen finden, jedoch unterscheiden sich die Schwerpunkte. Die unendliche Geschichte ist ein komplexes Werk und behandelt sowohl die innere Reise, als auch, dass die Wünsche und Entscheidungen immer Konsequenzen haben müssen. Eine Woche voller Samstage widersetzt sich den Normen der Gesellschaft. Die Hauptkritik in Krabat ist die Gefahr mit Macht und Unterdrückung wie in einer Diktatur. Wir pfeifen auf den Gurkenkönig behandelt in erster Hand die Gleichberechtigungsfrage innerhalb der Familienstruktur und gegenüber dem autoritären Vater. Die Romane spiegeln die damalige Zeit und deswegen kann man diesen vier Romanen aus der Phantastik der 1970er Jahren die Rolle als kritischer Gesellschaftsprüfer zuschreiben.

The object of the thesis is the computational complexity of certain combinatorial optimisation problems called \emph{valued constraint satisfaction problems}, or \emph{VCSPs} for short. The requirements and optimisation criteria of these problems are expressed by sums of \emph{(valued) constraints} (also called \emph{cost functions}). More precisely, the input of a VCSP consists of a finite set of variables, a finite set of cost functions that depend on these variables, and a cost $u$; the task is to find values for the variables such that the sum of the cost functions is at most $u$. By restricting the set of possible cost functions in the input, a great variety of computational optimisation problems can be modelled as VCSPs. Recently, the computational complexity of all VCSPs for finite sets of cost functions over a finite domain has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear (PL) and piecewise linear homogeneous (PLH) cost functions. The VCSP for a finite set of PLH cost functions can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by (polynomial-time many-one) reducing the problem to a finite-domain VCSP which can be solved using a linear programming relaxation. We apply this result to show the polynomial-time tractability of VCSPs for {\it submodular} PLH cost functions, for {\it convex} PLH cost functions, and for {\it componentwise increasing} PLH cost functions; in fact, we show that submodular PLH functions and componentwise increasing PLH functions form maximally tractable classes of PLH cost functions. We define the notion of {\it expressive power} for sets of cost functions over arbitrary domains, and discuss the relation between the expressive power and the set of fractional operations improving the same set of cost functions over an arbitrary countable domain. Finally, we provide a polynomial-time algorithm solving the restriction of the VCSP for {\it all} PL cost functions to a fixed number of variables.