The subject of the thesis are vector-valued Markov Games. Chapter 1 presents the idea, that has led to the development of the theory of general stochastic games. The work of Lloyd S. Shapley is outlined, and the most important authors and bibliography are stated. Also, the motivation behind the research of vector-valued game-theoretic problems is presented. Chapter 2 develops a rigorous mathematical model of vector-valued N-person Markov games. The corresponding definitions are stated, and the notations, as well as the notion of a strategy are explained in detail. On the basis of these definitions a probability measure is constructed, in an appropriate probability space, which controls the stochastic game process. Furthermore, as in all models of stochastic control, a payoff is specified, in our case the expected discounted payoff. The principles of vector optimization are stated in Chapter 3, and the concept of optimality with recpect to some convex cone is developed. This leads to the generalization of Nash-equilibria from scalar- to vector-valued games, the so-called D-equilibria. Examples are provided to show, that this definition really is a generalization of the existing definitions for scalar-valued games. For a given convex cone D, necessary and sufficient conditions are found to show, when a strategy is also a D-equilibrium. Furthermore it is shown that a D-equilibrium in stationary strategies exists, as one could expect from the known results from the theory of scalar-valued stochastic games. The main result of this chapter is a generalization of an existing result for 2-person vector-valued Markov games to N-person Markov Games, namely that a D-equilibrium of an N-person Markov game is a subgradient of specially constructed support functions of the original payoff functions. To be able to develop solution procedures in the simplest case, that is, the 2-person zero-sum case, Chapter 4 introduces the Denardo dynamic programming formalism. In the space of all p-dimensional functions we define a dynamic programming operator H? to describe the solutions of Markov games. The first of the two main results in this chapter is the following: the expected overall payoff to player 1, f(??), for a fixed stationary strategy ??, is the fixed point of the operator H?. The second theorem then shows, that the latter result is exactly the vector-valued generalization of the famous Shapley result. These theorems are fundamental for the subsequent development of two algorithms, the successive approximations and the Hoffman-Karp algorithm. A numerical example for both algorithms is presented. Chapter 4 finishes with a discussion on other significant results, and the outline of the further research. The Appendix finally presents the main results from general Game Theory, most of which were used for developing both theoretic and algorithmic parts of this thesis. / Das Thema der vorliegenden Arbeit sind vektorwertige Markov-Spiele. Im Kapitel 1 wird die Idee vorgestellt, die zur Entwicklung genereller stochastischer Spiele geführt hat. Die Arbeit von Lloyd S. Shapley wird kurz dargestellt, und die wichtigsten Autoren und Literaturquellen werden genannt. Es wird weiter die Motivation für das Studium der vektorwertigen Spiele erklärt. Kapitel 2 entwickelt ein allgemeines mathematisches Modell vektorwertiger N-Personen Markov-Spiele. Die entsprechenden Definitionen werden angegeben, und es wird auf die Bezeichnungen, sowie den Begriff einer Strategie eingegangen. Weiter wird im entsprechenden Wahrscheinlichkeitsraum ein Wahrscheinlichkeitsmaß konstruiert, das den zugrunde liegenden stochastischen Prozeß steuert. Wie bei allen Modellen gesteuerter stochastischen Prozesse wird eine Auszahlung spezifiziert, konkret der erwartete diskontierte Gesamtertrag. Im Kapitel 3 werden die Prinzipien der Vektoroptimierung erläutert. Es wird der Begriff der Optimalität bezüglich gegebener konvexer Kegel entwickelt. Dieser Begriff wird weiter benutzt, um die Definition der Nash-Gleichgewichte für skalarwertige Spiele auf unser vektorwertiges Modell, die sogenannten D-Gleichgewichte, zu erweitern. Anhand mehrerer Beispiele wird gezeigt, dass diese Definition eine Verallgemeinerung der existierenden Definitionen für skalarwertige Spiele ist. Weiter werden notwendige und hinreichende Bedingungen hinsichtlich des Optimierungskegels D angegeben, wann eine Strategie ein D-Gleichgewicht ist. Anschließend wird gezeigt, dass man sich ? wie bei Markov'schen Entscheidungsprozessen und skalarwertigen stochastischen Spielen - beim Suchen der D-Gleichgewichte auf stationäre Strategien beschränken kann. Das Hauptresultat dieses Kapitels ist die Verallgemeinerung einer schon bekannten Aussage für 2-Personen Markov-Spiele auf N-Personen Markov-Spiele: Ein D-Gleichgewicht im N-Personen Markov-Spiel ist ein Subgradient speziell konstruierter Trägerfunktionen des Gesamtertrags der Spieler. Um im einfachsten Fall der Markov-Spiele, den Zwei-Personen Nullsummenspielen, ein Lösungskonzept entwickeln zu können, wird im Kapitel 4 die Methode des Dynamischen Programmierens benutzt. Es wird der Denardo-Formalismus übernommen, um einen Operator H? im Raum aller p-dimensionalen vektorwertigen Funktionen zu entwickeln. Die Haputresultate dieses Kapitels sind zwei Sätze über optimale Lösungen, bzw. D-Gleichgewichte. Der erste Satz zeigt, dass für eine fixierte stationäre Strategie ?? der erwartete diskontierte Gesamtertrag f(??) der Fixpunkt des Operators H? ist. Anschließend zeigt der zweite Satz, dass diese Lösung genau der vektorwertigen Erweiterung des Resultats von Shapley entspricht. Anhand dieser Resultate werden nun zwei Algorithmen entwickelt: sukzessive Approximationen und Hoffman-Karp-Algorithmus. Es wird ein numerisches Beispiel für beide Algorithmen berechnet. Kapitel 4 schließt mit dem Abschnitt über weitere Resultate und Ansätze für weitere Forschung. Im Anhang werden die Hauptresultate der statischen Spieltheorie vorgestellt, viele von denen werden in der vorliegenden Arbeit benutzt.

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst. / For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required.

We present an axiomatization of relational varieties, i.e., classes of relational structures closed under formation of products and retracts, by a certain class of first-order sentences. We apply this result to categorically equivalent algebras and primal algebras. We consider the relational varieties generated by structures with minimal clone, rigid structures and two-element structures.

gekürzte Fassung: Coalgebren wurden sowohl in der Mathematik (seit den 70er Jahren) als auch in der theoretischen Informatik (seit den 90er Jahren) untersucht. In der Mathematik sind Coalgebren dual zu universellen Algebren definiert. Sie bestehen aus einer Trägermenge A zusammen mit Cofunktionen ? : A ? , die A in die n-fache disjunkte Vereinigung von sich selbst abbilden. Das Ziel der Forschung ist hier vor allem, duale Versionen von Definitionen und Resultaten aus der universellen Algebra für die Welt der Coalgebren zu finden. Die theoretische Informatik betrachtet Coalgebren von kategorieller Seite aus. Für einen gegebenen Funktor F : C ? C sind Coalgebren als Paare (S,"alpha") definiert, wobei S ein Objekt von C und "alpha" : S ? F(S) ein Morphismus in C ist. Somit stellt der obige Ansatz mit Cofunktionen einen Spezialfall dar. Begriffe wie Homomorphismus oder Bisimularität lassen sich auf einfache Weise ausdrücken und handhaben. Solche Coalgebren modellieren eine große Anzahl von dynamischen Systemen. Das liefert eine kanonische und vereinheitlichende Sicht auf diese Systeme. Die vorliegende Dissertation führt beide genannten Forschungsrichtungen der Coalgebren weiter: Teil I beschäftigt sich mit "klassischen" Coalgebren, also solchen, wie sie in der universellen Algebra untersucht werden. Insbesondere wird das Verhältnis zur Klontheorie erforscht. Teil II der Arbeit widmet sich dem kategoriellen Ansatz aus der theoretischen Informatik. Von speziellem Interesse ist hier die Anwendung von Coalgebren zur Spezifikation von Systemen. Coalgebren und Klontheorie In der universellen Algebra spielen Systeme von Funktionen eine bedeutende Rolle, u.a. in der Klontheorie. Dort betrachtet man Funktionen auf einer festen gegebenen Grundmenge. Klone von Funktionen sind Mengen von Funktionen, die alle Projektionen enthalten und die gegen Superposition (d.h. Einsetzen) abgeschlossen sind. Extern lassen sich diese Klone als Galois-abgeschlossene Mengengzgl. der Galois-Verbindung zwischen Funktionen und Relationen darstellen. Diese Galois-Verbindung wird durch die Eigenschaft einer Funktion induziert, eine Relation zu bewahren. Dual zu Klonen von Funktionen wurde von B. Csákány auch Klone von Cofunktionen untersucht. Folglich stellt sich die Frage, ob solche Klone ebenfalls mittels einer geeigneten Galois-Verbindung charakterisiert werden können. Die vorliegende Arbeit führt zunächst den Begriff von Corelationen ein. Es wird auf kanonische Weise definiert, was es heißt, daß eine Cofunktion eine Corelation bewahrt. Dies mündet in einer Galois-Theorie, deren Galois-abgeschlossene Mengen von Cofunktionen tatsächlich genau die Klone von Cofunktionen sind. Überdies entsprechen die Galois-abgeschlossenen Mengen von Corelationen genau den Klonen von Corelationen. Die Galois-Theorien von Funktionen und Relationen einerseits und Cofunktionen und Corelationen anderseits sind sich sehr ähnlich. Das wirft die Frage auf, welche Voraussetzungen allgemein nötig sind, um solche und ähnliche Galois-Theorien aufzustellen und die entsprechenden Galois-abgeschlossenen Mengen zu charakterisieren. Das Ergebnis ist eine Metatheorie, bei der die Gemeinsamkeiten in den Charakterisierungen der Galois-abgeschlossenen Mengen herausgearbeitet sind. Bereits bekannte Galois-Theorien erweisen sich als Spezialfälle dieser Metatheorie, und zwar die Galois-Theorien von partiellen Funktionen und Relationen, von mehrwertigen Funktionen und Relationen und von einstelligen Funktionen und Relationen....

The thesis deals with a general access to topological transversality in uniform spaces. / Die Arbeit behandelt einen allgemeinen Zugang zur Topologischen Transversalität in uniformen Räumen.

Wir untersuchen ein Defektkorrekturverfahren, das ein einfaches Upwind-Differenzenverfahren erster Ordnung mit einem zentralen Differenzenverfahren kombiniert, für ein- und zweidimensionale singulär gestörte Konvektions-Diffusions-Probleme auf einer Klasse von Shishkin-Typ-Gittern. Im eindimensionalen Fall wird nachgewiesen, dass das Verfahren von (fast) zweiter Ordnung, gleichmäßig bezüglich des Diffusionsparameters $\epsilon$ konvergiert. Zur Konvergenzanalyse für das zweidimensionale Modellproblem werden verschiedene Techniken diskutiert. In einem Spezialfall kann auf einem stückweise uniformen Shishkin-Gitter die $\epsilon$-gleichmäßige Konvergenz des Verfahrens von fast zweiter Ordnung gezeigt werden. Ferner sind die bisher bekannten Stabilitätsaussagen und ihre Verwendung zur Konvergenzanalysis der betrachteten Differenzenverfahren sowie Methoden zur Analyse von Defektkorrekturverfahren zusammengestellt. Einige Bemerkungen zu Defektkorrekturverfahren und Finite-Elemente-Methoden schließen die Arbeit ab. Numerische Experimente untermauern die theoretischen Resultate. / We consider a defect correction method that combines a first-order upwinded difference scheme with a second-order central difference scheme for model singularly perturbed convection-diffusion problems in one and two dimensions on a class of Shishkin-Type meshes. In one dimension, the method is shown to be convergent uniformly in the diffusion parameter $\epsilon$ of second order in the discrete maximum norm. To analyze the two-dimensional case, we discuss several proof techniques for defect correction methods. For a special problem with constant coefficients on a piecewise uniform Shishkin-mesh we can show the second order convergence of the considered scheme, uniformly with respect to the diffusion parameter. Moreover the known stability properties and their impact on the convergence analysis of the considered differnce schemes are compiled. Some remarks on defect correction and finite elements conclude the theses. Numerical experiments support our theoretical results.

No description available.

Bei der Berechnung von Adjungierten, zum Debuggen und für ähnliche Anwendungen kann man die Umkehr der entsprechenden Programmauswertung verwenden. Der einfachste Ansatz, nämlich das Mitschreiben einer kompletten Mitschrift der Vorwärtsrechnung, welche anschließend rückwärts gelesen wird, verursacht einen enormen Speicherplatzbedarf. Als Alternative dazu kann man die Mitschrift auch stückweise erzeugen, indem die Programmauswertung von passend gewählten Checkpoints wiederholt gestartet wird. Das Ziel der Arbeit ist die Minimierung des von der Programmumkehr verursachten Zeit- und Speicherplatzbedarfs. Dieser wird gemessen in Auswertungswiederholungen bzw. verwendeten Checkpoints. Optimale Umkehrschemata werden für Ein- und Mehr-Schritt-Verfahren entwickelt, welche zum Beispiel bei der Diskretisierung einer gewöhnlichen Differentialgleichung Verwendung finden. Desweiteren erfolgte die Entwicklung von parallelen Umkehrschemata, d. h. mehrere Prozessoren werden für die Umkehrung der Programmauswertung eingesetzt. Diese zusätzlichen Prozessoren dienen dazu, die wiederholten Berechnungen des Programms zu parallelisieren, so daß ein Prozessor die Rückwartsrechnung ohne Unterbrechung durchführen kann. Sowohl für die seriellen als auch für die parallelen Umkehrschemata wurde gezeigt, daß die Länge der umzukehrenden Programmauswertung exponentiell in Abhängigkeit von der Zahl der verwendeten Checkpoints und der Zahl der wiederholten Auswertungen bzw. verwendeten Prozessoren wächst. / For adjoint calculations, parameter estimation, and similar purposes one may need to reverse the execution of a computer program. The simplest option is to record a complete execution log and then to read it backwards. This requires massive amounts of storage. Instead one may generate the execution log piecewise by restarting the ``forward'' calculation repeatedly from suitably placed checkpoints. The basic structure of the resulting reversal schedules is illustrated. Various strategies are analysed with respect to the resulting temporal and spatial complexity on serial and parallel machines. For serial machines known optimal compromises between operations count and memory requirement are explained, and they are extended to more general situations. For program execution reversal on multi-processors the new challenges and demands on an optimal reversal schedule are described. We present parallel reversal schedules that are provably optimal with regards to the number of concurrent processes and the total amount of memory required.

We present an axiomatization of relational varieties, i.e., classes of relational structures closed under formation of products and retracts, by a certain class of first-order sentences. We apply this result to categorically equivalent algebras and primal algebras. We consider the relational varieties generated by structures with minimal clone, rigid structures and two-element structures.

The subject of the thesis are vector-valued Markov Games. Chapter 1 presents the idea, that has led to the development of the theory of general stochastic games. The work of Lloyd S. Shapley is outlined, and the most important authors and bibliography are stated. Also, the motivation behind the research of vector-valued game-theoretic problems is presented. Chapter 2 develops a rigorous mathematical model of vector-valued N-person Markov games. The corresponding definitions are stated, and the notations, as well as the notion of a strategy are explained in detail. On the basis of these definitions a probability measure is constructed, in an appropriate probability space, which controls the stochastic game process. Furthermore, as in all models of stochastic control, a payoff is specified, in our case the expected discounted payoff. The principles of vector optimization are stated in Chapter 3, and the concept of optimality with recpect to some convex cone is developed. This leads to the generalization of Nash-equilibria from scalar- to vector-valued games, the so-called D-equilibria. Examples are provided to show, that this definition really is a generalization of the existing definitions for scalar-valued games. For a given convex cone D, necessary and sufficient conditions are found to show, when a strategy is also a D-equilibrium. Furthermore it is shown that a D-equilibrium in stationary strategies exists, as one could expect from the known results from the theory of scalar-valued stochastic games. The main result of this chapter is a generalization of an existing result for 2-person vector-valued Markov games to N-person Markov Games, namely that a D-equilibrium of an N-person Markov game is a subgradient of specially constructed support functions of the original payoff functions. To be able to develop solution procedures in the simplest case, that is, the 2-person zero-sum case, Chapter 4 introduces the Denardo dynamic programming formalism. In the space of all p-dimensional functions we define a dynamic programming operator H? to describe the solutions of Markov games. The first of the two main results in this chapter is the following: the expected overall payoff to player 1, f(??), for a fixed stationary strategy ??, is the fixed point of the operator H?. The second theorem then shows, that the latter result is exactly the vector-valued generalization of the famous Shapley result. These theorems are fundamental for the subsequent development of two algorithms, the successive approximations and the Hoffman-Karp algorithm. A numerical example for both algorithms is presented. Chapter 4 finishes with a discussion on other significant results, and the outline of the further research. The Appendix finally presents the main results from general Game Theory, most of which were used for developing both theoretic and algorithmic parts of this thesis. / Das Thema der vorliegenden Arbeit sind vektorwertige Markov-Spiele. Im Kapitel 1 wird die Idee vorgestellt, die zur Entwicklung genereller stochastischer Spiele geführt hat. Die Arbeit von Lloyd S. Shapley wird kurz dargestellt, und die wichtigsten Autoren und Literaturquellen werden genannt. Es wird weiter die Motivation für das Studium der vektorwertigen Spiele erklärt. Kapitel 2 entwickelt ein allgemeines mathematisches Modell vektorwertiger N-Personen Markov-Spiele. Die entsprechenden Definitionen werden angegeben, und es wird auf die Bezeichnungen, sowie den Begriff einer Strategie eingegangen. Weiter wird im entsprechenden Wahrscheinlichkeitsraum ein Wahrscheinlichkeitsmaß konstruiert, das den zugrunde liegenden stochastischen Prozeß steuert. Wie bei allen Modellen gesteuerter stochastischen Prozesse wird eine Auszahlung spezifiziert, konkret der erwartete diskontierte Gesamtertrag. Im Kapitel 3 werden die Prinzipien der Vektoroptimierung erläutert. Es wird der Begriff der Optimalität bezüglich gegebener konvexer Kegel entwickelt. Dieser Begriff wird weiter benutzt, um die Definition der Nash-Gleichgewichte für skalarwertige Spiele auf unser vektorwertiges Modell, die sogenannten D-Gleichgewichte, zu erweitern. Anhand mehrerer Beispiele wird gezeigt, dass diese Definition eine Verallgemeinerung der existierenden Definitionen für skalarwertige Spiele ist. Weiter werden notwendige und hinreichende Bedingungen hinsichtlich des Optimierungskegels D angegeben, wann eine Strategie ein D-Gleichgewicht ist. Anschließend wird gezeigt, dass man sich ? wie bei Markov'schen Entscheidungsprozessen und skalarwertigen stochastischen Spielen - beim Suchen der D-Gleichgewichte auf stationäre Strategien beschränken kann. Das Hauptresultat dieses Kapitels ist die Verallgemeinerung einer schon bekannten Aussage für 2-Personen Markov-Spiele auf N-Personen Markov-Spiele: Ein D-Gleichgewicht im N-Personen Markov-Spiel ist ein Subgradient speziell konstruierter Trägerfunktionen des Gesamtertrags der Spieler. Um im einfachsten Fall der Markov-Spiele, den Zwei-Personen Nullsummenspielen, ein Lösungskonzept entwickeln zu können, wird im Kapitel 4 die Methode des Dynamischen Programmierens benutzt. Es wird der Denardo-Formalismus übernommen, um einen Operator H? im Raum aller p-dimensionalen vektorwertigen Funktionen zu entwickeln. Die Haputresultate dieses Kapitels sind zwei Sätze über optimale Lösungen, bzw. D-Gleichgewichte. Der erste Satz zeigt, dass für eine fixierte stationäre Strategie ?? der erwartete diskontierte Gesamtertrag f(??) der Fixpunkt des Operators H? ist. Anschließend zeigt der zweite Satz, dass diese Lösung genau der vektorwertigen Erweiterung des Resultats von Shapley entspricht. Anhand dieser Resultate werden nun zwei Algorithmen entwickelt: sukzessive Approximationen und Hoffman-Karp-Algorithmus. Es wird ein numerisches Beispiel für beide Algorithmen berechnet. Kapitel 4 schließt mit dem Abschnitt über weitere Resultate und Ansätze für weitere Forschung. Im Anhang werden die Hauptresultate der statischen Spieltheorie vorgestellt, viele von denen werden in der vorliegenden Arbeit benutzt.