TY - JOUR A1 - Edeko, Nikolai A1 - Gerlach, Moritz Reinhardt A1 - Kühner, Viktoria T1 - Measure-preserving semiflows and one-parameter Koopman semigroups JF - Semigroup forum N2 - For a finite measure space X, we characterize strongly continuous Markov lattice semigroups on Lp(X) by showing that their generator A acts as a derivation on the dense subspace D(A)L(X). We then use this to characterize Koopman semigroups on Lp(X) if X is a standard probability space. In addition, we show that every measurable and measure-preserving flow on a standard probability space is isomorphic to a continuous flow on a compact Borel probability space. KW - Measure-preserving semiflow KW - Koopman semigroup KW - Derivation KW - Topological model Y1 - 2019 U6 - https://doi.org/10.1007/s00233-018-9960-3 SN - 0037-1912 SN - 1432-2137 VL - 98 IS - 1 SP - 48 EP - 63 PB - Springer CY - New York ER - TY - JOUR A1 - Gerlach, Moritz Reinhardt A1 - Glück, Jochen T1 - Lower bounds and the asymptotic behaviour of positive operator semigroups JF - Ergodic theory and dynamical systems N2 - If (T-t) is a semigroup of Markov operators on an L-1-space that admits a nontrivial lower bound, then a well-known theorem of Lasota and Yorke asserts that the semigroup is strongly convergent as t -> infinity. In this article we generalize and improve this result in several respects. First, we give a new and very simple proof for the fact that the same conclusion also holds if the semigroup is merely assumed to be bounded instead of Markov. As a main result, we then prove a version of this theorem for semigroups which only admit certain individual lower bounds. Moreover, we generalize a theorem of Ding on semigroups of Frobenius-Perron operators. We also demonstrate how our results can be adapted to the setting of general Banach lattices and we give some counterexamples to show optimality of our results. Our methods combine some rather concrete estimates and approximation arguments with abstract functional analytical tools. One of these tools is a theorem which relates the convergence of a time-continuous operator semigroup to the convergence of embedded discrete semigroups. Y1 - 2017 U6 - https://doi.org/10.1017/etds.2017.9 SN - 0143-3857 SN - 1469-4417 VL - 38 SP - 3012 EP - 3041 PB - Cambridge Univ. Press CY - New York ER - TY - JOUR A1 - Gerlach, Moritz Reinhardt A1 - Glück, Jochen T1 - Mean ergodicity vs weak almost periodicity JF - Studia mathematica N2 - We provide explicit examples of positive and power-bounded operators on c(0) and l(infinity) which are mean ergodic but not weakly almost periodic. As a consequence we prove that a countably order complete Banach lattice on which every positive and power-bounded mean ergodic operator is weakly almost periodic is necessarily a KB-space. This answers several open questions from the literature. Finally, we prove that if T is a positive mean ergodic operator with zero fixed space on an arbitrary Banach lattice, then so is every power of T . KW - positive operators KW - weakly almost periodic KW - order continuous norm KW - KB-space KW - mean ergodic Y1 - 2019 U6 - https://doi.org/10.4064/sm170918-20-3 SN - 0039-3223 SN - 1730-6337 VL - 248 IS - 1 SP - 45 EP - 56 PB - Polska Akademia Nauk, Instytut Matematyczny CY - Warszawa ER - TY - JOUR A1 - Zass, Alexander T1 - Gibbs point processes on path space BT - existence, cluster expansion and uniqueness JF - Markov processes and related fields N2 - We present general existence and uniqueness results for marked models with pair interactions, exemplified through Gibbs point processes on path space. More precisely, we study a class of infinite-dimensional diffusions under Gibbsian interactions, in the context of marked point configurations: the starting points belong to R-d, and the marks are the paths of Langevin diffusions. We use the entropy method to prove existence of an infinite-volume Gibbs point process and use cluster expansion tools to provide an explicit activity domain in which uniqueness holds. KW - marked Gibbs point processes KW - DLR equations KW - uniqueness KW - cluster KW - expansion KW - infinite-dimensional diffusions Y1 - 2021 U6 - https://doi.org/10.20347/WIAS.PREPRINT.2859 SN - 1024-2953 VL - 28 IS - 3 SP - 329 EP - 364 PB - Polymat CY - Moscow ER - TY - THES A1 - Fischer, Florian T1 - Hardy inequalities on graphs T1 - Hardy-Ungleichungen auf Graphen N2 - Die Dissertation befasst sich mit einer zentralen Ungleichung der nicht-linearen Potentialtheorie, der Hardy-Ungleichung. Sie besagt, dass das nicht-lineare Energiefunktional von unten durch eine p-te Potenz einer gewichteten p-Norm abgeschätzt werden kann, p>1. Das Energiefunktional besteht dabei aus einem Divergenz- und einem beliebigen Potentialteil. Als zugrundeliegender Raum wurden hier lokal summierbare unendliche Graphen gewählt. Bisherige Veröffentlichungen zu Hardy-Ungleichungen auf Graphen haben vor allem den Spezialfall p=2 betrachtet, oder lokal endliche Graphen ohne Potentialteil. Zwei grundlegende Fragestellungen ergeben sich nun ganz natürlich: Für welche Graphen gibt überhaupt es eine Hardy-Ungleichung? Und, wenn es sie gibt, gibt es einen Weg um ein optimales Gewicht zu erhalten? Antworten auf diese Fragen werden in Theorem 10.1 und Theorem 12.1 gegeben. Theorem 10.1 gibt eine Reihe an Charakterisierungen an; unter anderem gibt es eine Hardy-Ungleichung auf einem Graphen genau dann, wenn es eine Greensche Funktion gibt. Theorem 12.1 gibt eine explizite Formel an, um optimale Hardy-Gewichte für lokal endliche Graphen unter einigen technischen Zusatzannahmen zu berechnen. In Beispielen wird gezeigt, dass Greensche Funktionen gute Kandidaten sind um in die Formel eingesetzt zu werden. Um diese beiden Theoreme beweisen zu können, müssen eine Vielzahl an Techniken erarbeitet werden, welche in den ersten Kapiteln behandelt werden. Dabei sind eine Verallgemeinerung der Grundzustandstransformation (Theorem 4.1), ein Agmon-Allegretto-Piepenbrink-artiges Resultat (Theorem 6.1) und das Vergleichsprinzip (Proposition 7.3) besonders hervorzuheben, da diese Resultate sehr häufig angewendet werden und somit das Fundament der Dissertation bilden. Es wird zudem darauf Wert gelegt die Theorie durch Beispiele zu veranschaulichen. Hierbei wird der Fokus auf die natürlichen Zahlen, Euklidische Gitter, Bäume und Sterne gelegt. Als Abschluss werden noch eine nicht-lineare Version der Heisenbergschen Unschärferelation und eine Rellich-Ungleichung aus der Hardy-Ungleichung geschlussfolgert. N2 - The dissertation deals with a central inequality of non-linear potential theory, the Hardy inequality. It states that the non-linear energy functional can be estimated from below by a pth power of a weighted p-norm, p>1. The energy functional consists of a divergence part and an arbitrary potential part. Locally summable infinite graphs were chosen as the underlying space. Previous publications on Hardy inequalities on graphs have mainly considered the special case p=2, or locally finite graphs without a potential part. Two fundamental questions now arise quite naturally: For which graphs is there a Hardy inequality at all? And, if it exists, is there a way to obtain an optimal weight? Answers to these questions are given in Theorem 10.1 and Theorem 12.1. Theorem 10.1 gives a number of characterizations; among others, there is a Hardy inequality on a graph if and only if there is a Green's function. Theorem 12.1 gives an explicit formula to compute optimal Hardy weights for locally finite graphs under some additional technical assumptions. Examples show that Green's functions are good candidates to be used in the formula. Emphasis is also placed on illustrating the theory with examples. The focus is on natural numbers, Euclidean lattices, trees and star graphs. Finally, a non-linear version of the Heisenberg uncertainty principle and a Rellich inequality are derived from the Hardy inequality. KW - graph theory KW - Hardy inequality KW - quasi-linear potential theory KW - p-Laplacian KW - criticality theory KW - Graphentheorie KW - Hardy-Ungleichung KW - quasilineare Potentialtheorie KW - p-Laplace-Operator KW - Kritikalitätstheorie Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-647730 ER - TY - THES A1 - Hecher, Markus T1 - Advanced tools and methods for treewidth-based problem solving N2 - In the last decades, there was a notable progress in solving the well-known Boolean satisfiability (Sat) problem, which can be witnessed by powerful Sat solvers. One of the reasons why these solvers are so fast are structural properties of instances that are utilized by the solver’s interna. This thesis deals with the well-studied structural property treewidth, which measures the closeness of an instance to being a tree. In fact, there are many problems parameterized by treewidth that are solvable in polynomial time in the instance size when parameterized by treewidth. In this work, we study advanced treewidth-based methods and tools for problems in knowledge representation and reasoning (KR). Thereby, we provide means to establish precise runtime results (upper bounds) for canonical problems relevant to KR. Then, we present a new type of problem reduction, which we call decomposition-guided (DG) that allows us to precisely monitor the treewidth when reducing from one problem to another problem. This new reduction type will be the basis for a long-open lower bound result for quantified Boolean formulas and allows us to design a new methodology for establishing runtime lower bounds for problems parameterized by treewidth. Finally, despite these lower bounds, we provide an efficient implementation of algorithms that adhere to treewidth. Our approach finds suitable abstractions of instances, which are subsequently refined in a recursive fashion, and it uses Sat solvers for solving subproblems. It turns out that our resulting solver is quite competitive for two canonical counting problems related to Sat. N2 - In den letzten Jahrzehnten konnte ein beachtlicher Fortschritt im Bereich der Aussagenlogik verzeichnet werden. Dieser äußerte sich dadurch, dass für das wichtigste Problem in diesem Bereich, genannt „Sat“, welches sich mit der Fragestellung befasst, ob eine gegebene aussagenlogische Formel erfüllbar ist oder nicht, überwältigend schnelle Computerprogramme („Solver“) entwickelt werden konnten. Interessanterweise liefern diese Solver eine beeindruckende Leistung, weil sie oft selbst Probleminstanzen mit mehreren Millionen von Variablen spielend leicht lösen können. Auf der anderen Seite jedoch glaubt man in der Wissenschaft weitgehend an die Exponentialzeithypothese (ETH), welche besagt, dass man im schlimmsten Fall für das Lösen einer Instanz in diesem Bereich exponentielle Laufzeit in der Anzahl der Variablen benötigt. Dieser vermeintliche Widerspruch ist noch immer nicht vollständig geklärt, denn wahrscheinlich gibt es viele ineinandergreifende Gründe für die Schnelligkeit aktueller Sat Solver. Einer dieser Gründe befasst sich weitgehend mit strukturellen Eigenschaften von Probleminstanzen, die wohl indirekt und intern von diesen Solvern ausgenützt werden. Diese Dissertation beschäftigt sich mit solchen strukturellen Eigenschaften, nämlich mit der sogenannten Baumweite. Die Baumweite ist sehr gut erforscht und versucht zu messen, wie groß der Abstand von Probleminstanzen zu Bäumen ist (Baumnähe). Allerdings ist dieser Parameter sehr generisch und bei Weitem nicht auf Problemstellungen der Aussagenlogik beschränkt. Tatsächlich gibt es viele weitere Probleme, die parametrisiert mit Baumweite in polynomieller Zeit gelöst werden können. Interessanterweise gibt es auch viele Probleme in der Wissensrepräsentation (KR), von denen man davon ausgeht, dass sie härter sind als das Problem Sat, die bei beschränkter Baumweite in polynomieller Zeit gelöst werden können. Ein prominentes Beispiel solcher Probleme ist das Problem QSat, welches sich für die Gültigkeit einer gegebenen quantifizierten, aussagenlogischen Formel (QBF), das sind aussagenlogische Formeln, wo gewisse Variablen existenziell bzw. universell quantifiziert werden können, befasst. Bemerkenswerterweise wird allerdings auch im Zusammenhang mit Baumweite, ähnlich zu Methoden der klassischen Komplexitätstheorie, die tatsächliche Komplexität (Härte) solcher Problemen quantifiziert, wo man die exakte Laufzeitabhängigkeit beim Problemlösen in der Baumweite (Stufe der Exponentialität) beschreibt. Diese Arbeit befasst sich mit fortgeschrittenen, Baumweite-basierenden Methoden und Werkzeugen für Probleme der Wissensrepräsentation und künstlichen Intelligenz (AI). Dabei präsentieren wir Methoden, um präzise Laufzeitresultate (obere Schranken) für prominente Fragmente der Antwortmengenprogrammierung (ASP), welche ein kanonisches Paradigma zum Lösen von Problemen der Wissensrepräsentation darstellt, zu erhalten. Unsere Resultate basieren auf dem Konzept der dynamischen Programmierung, die angeleitet durch eine sogenannte Baumzerlegung und ähnlich dem Prinzip „Teile-und-herrsche“ funktioniert. Solch eine Baumzerlegung ist eine konkrete, strukturelle Zerlegung einer Probleminstanz, die sich stark an der Baumweite orientiert. Des Weiteren präsentieren wir einen neuen Typ von Problemreduktion, den wir als „decomposition-guided (DG)“, also „zerlegungsangeleitet“, bezeichnen. Dieser Reduktionstyp erlaubt es, Baumweiteerhöhungen und -verringerungen während einer Problemreduktion von einem bestimmten Problem zu einem anderen Problem präzise zu untersuchen und zu kontrollieren. Zusätzlich ist dieser neue Reduktionstyp die Basis, um ein lange offen gebliebenes Resultat betreffend quantifizierter, aussagenlogischer Formeln zu zeigen. Tatsächlich sind wir damit in der Lage, präzise untere Schranken, unter der Annahme der Exponentialzeithypothese, für das Problem QSat bei beschränkter Baumweite zu zeigen. Genauer gesagt können wir mit diesem Konzept der DG Reduktionen zeigen, dass das Problem QSat, beschränkt auf Quantifizierungsrang ` und parametrisiert mit Baumweite k, im Allgemeinen nicht besser als in einer Laufzeit, die `-fach exponentiell in der Baumweite und polynomiell in der Instanzgröße ist1, lösen. Dieses Resultat hebt auf nicht-inkrementelle Weise ein bekanntes Ergebnis für Quantifizierungsrang 2 auf beliebige Quantifizierungsränge, allerdings impliziert es auch sehr viele weitere Konsequenzen. Das Resultat über die untere Schranke des Problems QSat erlaubt es, eine neue Methodologie zum Zeigen unterer Schranken einer Vielzahl von Problemen der Wissensrepräsentation und künstlichen Intelligenz, zu etablieren. In weiterer Konsequenz können wir damit auch zeigen, dass die oberen Schranken sowie die DG Reduktionen dieser Arbeit unter der Hypothese ETH „eng“ sind, d.h., sie können wahrscheinlich nicht mehr signifikant verbessert werden. Die Ergebnisse betreffend der unteren Schranken für QSat und die dazugehörige Methodologie konstituieren in gewisser Weise eine Hierarchie von über Baumweite parametrisierte Laufzeitklassen. Diese Laufzeitklassen können verwendet werden, um die Härte von Problemen für das Ausnützen von Baumweite zu quantifizieren und diese entsprechend ihrer Laufzeitabhängigkeit bezüglich Baumweite zu kategorisieren. Schlussendlich und trotz der genannten Resultate betreffend unterer Schranken sind wir im Stande, eine effiziente Implementierung von Algorithmen basierend auf dynamischer Programmierung, die entlang einer Baumzerlegung angeleitet wird, zur Verfügung zu stellen. Dabei funktioniert unser Ansatz dahingehend, indem er probiert, passende Abstraktionen von Instanzen zu finden, die dann im Endeffekt sukzessive und auf rekursive Art und Weise verfeinert und verbessert werden. Inspiriert durch die enorme Effizienz und Effektivität der Sat Solver, ist unsere Implementierung ein hybrider Ansatz, weil sie den starken Gebrauch von Sat Solvern zum Lösen diverser Subprobleme, die während der dynamischen Programmierung auftreten, pflegt. Dabei stellt sich heraus, dass der resultierende Solver unserer Implementierung im Bezug auf Effizienz beim Lösen von zwei kanonischen, Sat-verwandten Zählproblemen mit bestehenden Solvern locker mithalten kann. Tatsächlich sind wir im Stande, Instanzen, wo die oberen Schranken von Baumweite 260 übersteigen, zu lösen. Diese überraschende Beobachtung zeigt daher, dass Baumweite ein wichtiger Parameter sein könnte, der wohl in modernen Designs von Solvern berücksichtigt werden sollte. KW - Treewidth KW - Dynamic Programming KW - Knowledge Representation and Reasoning KW - Artificial Intelligence KW - Computational Complexity KW - Parameterized Complexity KW - Answer Set Programming KW - Exponential Time Hypothesis KW - Lower Bounds KW - Algorithms KW - Algorithmen KW - Antwortmengenprogrammierung KW - Künstliche Intelligenz KW - Komplexitätstheorie KW - Dynamische Programmierung KW - Exponentialzeit Hypothese KW - Wissensrepräsentation und Schlussfolgerung KW - Untere Schranken KW - Parametrisierte Komplexität KW - Baumweite Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-512519 ER -