Refine
Has Fulltext
- yes (13)
Year of publication
- 2009 (13) (remove)
Document Type
- Preprint (13) (remove)
Keywords
- Automatisches Beweisen (1)
- DPLL (1)
- Edge-degenerate operators (1)
- Klausellernen (1)
- Logikkalkül (1)
- Operators on manifolds with conical singularities (1)
- SAT (1)
- automated theorem proving (1)
- clause learning (1)
- conormal symbols (1)
Many formal descriptions of DPLL-based SAT algorithms either do not include all essential proof techniques applied by modern SAT solvers or are bound to particular heuristics or data structures. This makes it difficult to analyze proof-theoretic properties or the search complexity of these algorithms. In this paper we try to improve this situation by developing a nondeterministic proof calculus that models the functioning of SAT algorithms based on the DPLL calculus with clause learning. This calculus is independent of implementation details yet precise enough to enable a formal analysis of realistic DPLL-based SAT algorithms.
We give a survey on the calculus of (pseudo-differential) boundary value problems with the transmision property at the boundary, and ellipticity in the Shapiro-Lopatinskij sense. Apart from the original results of the work of Boutet de Monvel we present an approach based on the ideas of the edge calculus. In a final section we introduce symbols with the anti-transmission property.
Multitype branching processes and Feller diffusion processes are conditioned on very late extinction. The conditioned laws are expressed as Doob h-transforms of the unconditioned laws, and an interpretation of the conditioned paths for the branching process is given, via the immortal particle. We study different limits for the conditioned process (increasing delay of extinction, long-time behavior, scaling limit) and provide an exhaustive list of exchangeability results.
Zufällige Punktprozesse beschreiben eine (zufällige) zeitliche Abfolge von Ereignissen oder eine (zufällige) räumliche Anordnung von Objekten. Deren wichtigster Vertreter ist der Poissonprozess. Der Poissonprozess zum Intensitätsmaß, das Lebesgue-Maß ordnet jedem Gebiet sein Volumen zu, erzeugt lokal, d.h in einem beschränkten Gebiet B, gerade eine mit dem Volumen von B poissonverteilte Anzahl von Punkten, die identisch und unabhängig voneinander in B plaziert werden; im Mittel ist diese Anzahl (B). Ersetzt man durch ein Vielfaches a, so wird diese Anzahl mit dem a-fachen Mittelwert erzeugt. Poissonprozesse, die im gesamten Raum unendlich viele Punkte realisieren, enthalten bereits in einer einzigen Stichprobe genügend Informationen, um Statistik betreiben zu können: Bedingt man lokal bzgl. der Anzahl der Teilchen einer Stichprobe, so fragt man nach allen Punktprozessen, die eine solche Beobachtung hätten liefern können. Diese sind Limespunktprozesse zu dieser Beobachtung. Kommt mehr als einer in Frage, spricht man von einem Phasenübergang. Da die Menge dieser Limespunktprozesse konvex ist, fragt man nach deren Extremalpunkten, dem Rand. Im ersten Teil wird ein Poissonprozess für ein physikalisches Teilchenmodell für Bosonen konstruiert. Dieses erzeugt sogenannte Loops, das sind geschlossene Polygonzüge, die dadurch charakterisiert sind, dass man an einem Ort mit einem Punkt startet, den mit einem normalverteilten Schritt läuft und dabei nach einer gegebenen, aber zufälligen Anzahl von Schritten zum Ausgangspunkt zurückkehrt. Für verschiedene Beobachtungen von Stichproben werden zugehörige Limespunktprozesse diskutiert. Diese Beobachtungen umfassen etwa das Zählen der Loops gemäaß ihrer Länge, das Zählen der Loops insgesamt, oder das Zählen der von den Loops gemachten Schritte. Jede Wahl zieht eine charakteristische Struktur der invarianten Punktprozesse nach sich. In allen hiesigen Fällen wird ein charakteristischer Phasenübergang gezeigt und Extremalpunkte werden als spezielle Poissonprozesse identifiziert. Insbesondere wird gezeigt, wie die Wahl der Beobachtung die Länge der Loops beeinflusst. Geometrische Eigenschaften dieser Poissonprozesse sind der Gegenstand des zweiten Teils der Arbeit. Die Technik der Palmschen Verteilungen eines Punktprozesses erlaubt es, unter den unendlich vielen Loops einer Realisierung den typischen Loop herauszupicken, dessen Geometrie dann untersucht wird. Eigenschaften sind unter anderem die euklidische Länge eines Schrittes oder, nimmt man mehrere aufeinander folgende Schritte, das Volumen des von ihnen definierten Simplex. Weiterhin wird gezeigt, dass der Schwerpunkt eines typischen Loops normalverteilt ist mit einer festen Varianz. Der dritte und letzte Teil befasst sich mit der Konstruktion, den Eigenschaften und der Statistik eines neuartigen Punktprozesses, der Polyascher Summenprozess genannt wird. Seine Konstruktion verallgemeinert das Prinzip der Polyaschen Urne: Im Gegensatz zum Poissonprozess, der alle Punkte unabhängig und vor allem identisch verteilt, werden hier die Punkte nacheinander derart verteilt, dass der Ort, an dem ein Punkt plaziert wird, eine Belohnung auf die Wahrscheinlichkeit bekommt, nach der nachfolgende Punkte verteilt werden. Auf diese Weise baut der Polyasche Summenprozess "Türmchen", indem sich verschiedene Punkte am selben Ort stapeln. Es wird gezeigt, dass dennoch grundlegende Eigenschaften mit denjenigen des Poissonprozesses übereinstimmen, dazu gehören unendliche Teilbarkeit sowie Unabhängigkeit der Zuwächse. Zudem werden sein Laplace-Funktional sowie seine Palmsche Verteilung bestimmt. Letztere zeigt, dass die Höhe der Türmchen gerade geometrisch verteilt ist. Abschließend werden wiederum Statistiken, nun für den Summenprozess, diskutiert. Je nach Art der Beobachtung von der Stichprobe, etwa Anzahl, Gesamthöhe der Türmchen oder beides, gibt es in jedem der drei Fälle charakteristische Limespunktprozesse und es stellt sich heraus, dass die zugehörigen Extremalverteilungen wiederum Polyasche Summenprozesse sind.
We consider an infinite system of non overlaping globules undergoing Brownian motions in R3. The term globules means that the objects we are dealing with are spherical, but with a radius which is random and time-dependent. The dynamics is modelized by an infinitedimensional Stochastic Differential Equation with local time. Existence and uniqueness of a strong solution is proven for such an equation with fixed deterministic initial condition. We also find a class of reversible measures.
Aus dem Inhalt: Einleitung Kapitel 1. Starke Gesetze der Grossen Zahlen 1. SGGZ unter Wachstumsbedingungen an die p-ten Momente 2. SGGZ für identisch verteilte Zufallsvariablen 3. SGGZ für Prozesse mit *-mixing-Eigenschaft Kapitel 2. Einführung zu diskreten (Sub-,Super-)Martingalen 1. Vorhersagbarkeit 2. gestoppte (Sub-,Super-)Martingale 3. Upcrossings 4. Konvergenzsätze 5. Doob-Zerlegung 6. Eine äquivalente Definition eines (Sub-)Martingals Kapitel 3. Martingale und gleichgradige Integrierbarkeit 1. Gleichmäßige(-f¨ormige,-gradige) Integrierbarkeit 2. gleichgradig integrierbare Martingale Kapitel 4. Martingale und das SGGZ Kapitel 5.”reversed“ (Sub-,Super-)Martingale 1. Konvergenzsätze Kapitel 6. (Sub-,Super-)Martingale mit gerichteter Indexmenge 1. Äquivalente Formulierung eines (Sub-)Martingals 2. Konvergenzsätze Kapitel 7. Quasimartingale,Amarts und Semiamarts 1. Konvergenzsätze 2. Riesz-Zerlegung 3. Doob-Zerlegung Kapitel 8. Amarts und das SGGZ Kapitel 9.”reversed“ Amarts und Semiamarts 1. Konvergenzsätze 2.”Aufwärts“- gegen ”Abwärts“-Adaptiertheit 3. Riesz-Zerlegung 4. Stabilitätsanalyse Kapitel 10. Amarts mit gerichteter Indexmenge 1. Konvergenzsätze 2. Riesz-Zerlegung Anhang A. zur Existenz einer Folge unabhängiger Zufallsvariablen B. Konvergenz
The Cauchy problem of the vacuum Einstein's equations aims to find a semimetric g(αβ) of a spacetime with vanishing Ricci curvature Rα,β and prescribed initial data. Under the harmonic gauge condition, the equations Rα,β = 0 are transferred into a system of quasi-linear wave equations which are called the reduced Einstein equations. The initial data for Einstein's equations are a proper Riemannian metric h(αβ) and a second fundamental form K(αβ). A necessary condition for the reduced Einstein equation to satisfy the vacuum equations is that the initial data satisfy Einstein constraint equations. Hence the data (h(αβ),K(αβ)) cannot serve as initial data for the reduced Einstein equations. Previous results in the case of asymptotically flat spacetimes provide a solution to the constraint equations in one type of Sobolev spaces, while initial data for the evolution equations belong to a different type of Sobolev spaces. The goal of our work is to resolve this incompatibility and to show that under the harmonic gauge the vacuum Einstein equations are well-posed in one type of Sobolev spaces.
We construct elliptic elements in the algebra of (classical pseudo-differential) operators on a manifold M with conical singularities. The ellipticity of any such operator A refers to a pair of principal symbols (σ0, σ1) where σ0 is the standard (degenerate) homogeneous principal symbol, and σ1 is the so-called conormal symbol, depending on the complex Mellin covariable z. The conormal symbol, responsible for the conical singularity, is operator-valued and acts in Sobolev spaces on the base X of the cone. The σ1-ellipticity is a bijectivity condition for all z of real part (n + 1)/2 − γ, n = dimX, for some weight γ. In general, we have to rule out a discrete set of exceptional weights that depends on A. We show that for every operator A which is elliptic with respect to σ0, and for any real weight γ there is a smoothing Mellin operator F in the cone algebra such that A + F is elliptic including σ1. Moreover, we apply the results to ellipticity and index of (operator-valued) edge symbols from the calculus on manifolds with edges.