Zugl.: Berlin, Humboldt-University, Habil.-Schr. / Lizenzpflichtig.

No description available.

Techn. Universiẗat, Diss., 2001--Berlin.

Humboldt-Univ., Habil.-Schr.--Berlin. / Literaturverz. S. [100] - 109.

We extend previous results on the complexity of solving language equations with one-sided concatenation and all Boolean operations to the case where also disequations (i.e., negated equations) may occur. To show that solvability of systems of equations and disequations is still in ExpTime, we introduce a new type of automata working on infinite trees, which we call looping automata with colors. As applications of these results, we show new complexity results for disunification in the description logic FL₀ and for monadic set constraints with negation. We believe that looping automata with colors may also turn out to be useful in other applications. / A short version of this report has also appeared in Proceedings of LPAR-18, Springer LNCS 7180, 2012.

The topic of this thesis is a diffusion process on a potential landscape which is given by a smooth Hamiltonian function in the regime of small noise. The work provides a new proof of the Eyring-Kramers formula for the Poincaré inequality of the associated generator of the diffusion. The Poincaré inequality characterizes the spectral gap of the generator and establishes the exponential rate of convergence towards equilibrium in the L²-distance. This result was first obtained by Bovier et. al. in 2004 relying on potential theory. The presented approach in the thesis generalizes to obtain also asymptotic sharp estimates of the constant in the logarithmic Sobolev inequality. The optimal constant in the logarithmic Sobolev inequality characterizes the convergence rate to equilibrium with respect to the relative entropy, which is a stronger distance as the L²-distance and slightly weaker than the L¹-distance. The optimal constant has here no direct spectral representation. The proof makes use of the scale separation present in the dynamics. The Eyring-Kramers formula follows as a simple corollary from the two main results of the work: The first one shows that the associated Gibbs measure restricted to a basin of attraction has a good Poincaré and logarithmic Sobolev constants providing the fast convergence of the diffusion to metastable states. The second main ingredient is a mean-difference estimate. Here a weighted transportation distance is used. It contains the main contribution to the Poincaré and logarithmic Sobolev constant, resulting from exponential long waiting times of jumps between metastable states of the diffusion.

Diese Arbeit befasst sich mit Untersuchung der Hölder Calmness, eines Stabilitätskonzeptes das man als Verallgemeinerung des Begriffs der Calmness erhält. Ausgehend von Charakterisierungen dieser Eigenschaft für Niveaumengen von Funktionen, werden, unter der Voraussetzung der Hölder Calmness, Prozeduren zur Bestimmung von Elementen dieser Mengen analysiert. Ebenso werden hinreichende Bedingungen für Hölder Calmness studiert. Da Hölder Calmness (nichtleerer) Lösungsmengen endlicher Ungleichungssysteme mittels (lokaler) Fehlerabschätzungen beschrieben werden kann, werden auch Erweiterungen der lokalen zu globalen Ergebnissen diskutiert. Als Anwendung betrachten wir speziell den Fall von Niveaumengen von Polynomen bzw. allgemeine Lösungsmengen polynomialer Gleichungen und Ungleichungen. Eine konkrete Frage, die wir beantworten wollen, ist die nach dem Zusammenhang zwischen dem größten Grad der beteiligten Polynome sowie dem Typ, d.h. dem auftretenden Exponenten, der Hölder Calmness des entsprechenden Systems. / This thesis is concerned with an analysis of Hölder calmness, a stability property derived from the concept of calmness. On the basis of its characterization for (sub)level sets, we will cogitate about procedures to determine points in such sets under a Hölder calmness assumption. Also sufficient conditions for Hölder calmness of (sub)level sets and of inequality systems will be given and examined. Further, since Hölder calmness of (nonempty) solution sets of finite inequality systems may be described in terms of (local) error bounds, we will as well amplify the local propositions to global ones. As an application we investigate the case of (sub)level sets of polynomials and of general solution sets of polynomial equations and inequalities. A concrete question we want to answer here is, in which way the maximal degree of the involved polynomials is connected to the exponent of Hölder calmness or of the error bound for the system in question.

The interaction between the study of geometric and analytic aspects of Riemannian manifolds and that of graphs is a very amazing subject. The study of synthetic curvature notions on graphs adds new contributions to this topic. In this thesis, we mainly study two kinds of synthetic curvature notions: the Ollivier-Ricci cuvature on locally finite graphs and the combinatorial curvature on infinite semiplanar graphs. In the first part, we study the Ollivier-Ricci curvature. As known in Riemannian geometry, a lower Ricci curvature bound prevents geodesics from diverging too fast on average. We translate this Riemannian idea into a combinatorial setting using the Olliver-Ricci curvature notion. Note that on a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. We derive lower and upper Ollivier-Ricci curvature bounds on graphs in terms of number of triangles, which is sharp for instance for complete graphs. We then describe the relation between Ollivier-Ricci curvature and the local clustering coefficient, which is an important concept in network analysis introduced by Watts-Strogatz. Furthermore, positive lower boundedness of Ollivier-Ricci curvature for neighboring vertices imply the existence of at least one triangle. It turns out that the existence of triangles can also improve Lin-Yau\'s curvature dimension inequality on graphs and then produce an implication from Ollivier-Ricci curvature lower boundedness to the curvature dimension inequality. The existence of triangles prevents a graph from being bipartite. A finite graph is bipartite if and only if its largest eigenvalue equals 2. Therefore it is natural that Ollivier-Ricci curvature is closely related to the largest eigenvalue estimates. We combine Ollivier-Ricci curvature notion with the neighborhood graph method developed by Bauer-Jost to study the spectrum estimates of a finite graph. We can always obtain nontrivial estimates on a non-bipartite graph even if its curvature is nonpositive. This answers one of Ollivier\'s open problem in the finite graph setting. In the second part of this thesis, we study systematically infinite semiplanar graphs with nonnegative combinatorial curvature. Unlike the previous Gauss-Bonnet formula approach, we explore an Alexandrov approach based on the observation that the nonnegative combinatorial curvature on a semiplanar graph is equivalent to nonnegative Alexandrov curvature on the surface obtained by replacing each face by a regular polygon of side length one with the same facial degree and gluing the polygons along common edges. Applying Cheeger-Gromoll splitting theorem on the surface, we give a metric classification of infinite semiplanar graphs with nonnegative curvature. We also construct the graphs embedded into the projective plane minus one point. Those constructions answer a question proposed by Chen. We further prove the volume doubling property and Poincare inequality which make the running of Nash-Moser iteration possible. We in particular explore the volume growth behavior on Archimedean tilings on a plane and prove that they satisfy a weak version of relative volume comparison with constant 1. With the above two basic inequalities in hand, we study the geometric function theory of infinite semiplanar graphs with nonnegative curvature. We obtain the Liouville type theorem for positive harmonic functions, the parabolicity. We also prove a dimension estimate for polynomial growth harmonic functions, which is an extension of the solution of Colding-Minicozzi of a conjecture of Yau in Riemannian geometry.

The topic of this thesis is a diffusion process on a potential landscape which is given by a smooth Hamiltonian function in the regime of small noise. The work provides a new proof of the Eyring-Kramers formula for the Poincaré inequality of the associated generator of the diffusion. The Poincaré inequality characterizes the spectral gap of the generator and establishes the exponential rate of convergence towards equilibrium in the L²-distance. This result was first obtained by Bovier et. al. in 2004 relying on potential theory. The presented approach in the thesis generalizes to obtain also asymptotic sharp estimates of the constant in the logarithmic Sobolev inequality. The optimal constant in the logarithmic Sobolev inequality characterizes the convergence rate to equilibrium with respect to the relative entropy, which is a stronger distance as the L²-distance and slightly weaker than the L¹-distance. The optimal constant has here no direct spectral representation. The proof makes use of the scale separation present in the dynamics. The Eyring-Kramers formula follows as a simple corollary from the two main results of the work: The first one shows that the associated Gibbs measure restricted to a basin of attraction has a good Poincaré and logarithmic Sobolev constants providing the fast convergence of the diffusion to metastable states. The second main ingredient is a mean-difference estimate. Here a weighted transportation distance is used. It contains the main contribution to the Poincaré and logarithmic Sobolev constant, resulting from exponential long waiting times of jumps between metastable states of the diffusion.

The interaction between the study of geometric and analytic aspects of Riemannian manifolds and that of graphs is a very amazing subject. The study of synthetic curvature notions on graphs adds new contributions to this topic. In this thesis, we mainly study two kinds of synthetic curvature notions: the Ollivier-Ricci cuvature on locally finite graphs and the combinatorial curvature on infinite semiplanar graphs. In the first part, we study the Ollivier-Ricci curvature. As known in Riemannian geometry, a lower Ricci curvature bound prevents geodesics from diverging too fast on average. We translate this Riemannian idea into a combinatorial setting using the Olliver-Ricci curvature notion. Note that on a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. We derive lower and upper Ollivier-Ricci curvature bounds on graphs in terms of number of triangles, which is sharp for instance for complete graphs. We then describe the relation between Ollivier-Ricci curvature and the local clustering coefficient, which is an important concept in network analysis introduced by Watts-Strogatz. Furthermore, positive lower boundedness of Ollivier-Ricci curvature for neighboring vertices imply the existence of at least one triangle. It turns out that the existence of triangles can also improve Lin-Yau\''s curvature dimension inequality on graphs and then produce an implication from Ollivier-Ricci curvature lower boundedness to the curvature dimension inequality. The existence of triangles prevents a graph from being bipartite. A finite graph is bipartite if and only if its largest eigenvalue equals 2. Therefore it is natural that Ollivier-Ricci curvature is closely related to the largest eigenvalue estimates. We combine Ollivier-Ricci curvature notion with the neighborhood graph method developed by Bauer-Jost to study the spectrum estimates of a finite graph. We can always obtain nontrivial estimates on a non-bipartite graph even if its curvature is nonpositive. This answers one of Ollivier\''s open problem in the finite graph setting. In the second part of this thesis, we study systematically infinite semiplanar graphs with nonnegative combinatorial curvature. Unlike the previous Gauss-Bonnet formula approach, we explore an Alexandrov approach based on the observation that the nonnegative combinatorial curvature on a semiplanar graph is equivalent to nonnegative Alexandrov curvature on the surface obtained by replacing each face by a regular polygon of side length one with the same facial degree and gluing the polygons along common edges. Applying Cheeger-Gromoll splitting theorem on the surface, we give a metric classification of infinite semiplanar graphs with nonnegative curvature. We also construct the graphs embedded into the projective plane minus one point. Those constructions answer a question proposed by Chen. We further prove the volume doubling property and Poincare inequality which make the running of Nash-Moser iteration possible. We in particular explore the volume growth behavior on Archimedean tilings on a plane and prove that they satisfy a weak version of relative volume comparison with constant 1. With the above two basic inequalities in hand, we study the geometric function theory of infinite semiplanar graphs with nonnegative curvature. We obtain the Liouville type theorem for positive harmonic functions, the parabolicity. We also prove a dimension estimate for polynomial growth harmonic functions, which is an extension of the solution of Colding-Minicozzi of a conjecture of Yau in Riemannian geometry.