Background: Dynamic programming algorithms provide exact solutions to many problems in computational biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions, and perform stochastic sampling. This is explained in the theory of Algebraic Dynamic Programming (ADP) by a strict separation of state space traversal (usually represented by a context free grammar), scoring (encoded as an algebra), and choice rule. A key ingredient in this theory is the use of yield parsers that operate on the ordered input data structure, usually strings or ordered trees. The computation of ensemble properties, such as a posteriori probabilities of HMMs or partition functions in RNA folding, requires the combination of two distinct, but intimately related algorithms, known as the inside and the outside recursion. Only the inside recursions are covered by the classical ADP theory. Results: The ideas of ADP are generalized to a much wider scope of data structures by relaxing the concept of parsing. This allows us to formalize the conceptual complementarity of inside and outside variables in a natural way. We demonstrate that outside recursions are generically derivable from inside decomposition schemes. In addition to rephrasing the well-known algorithms for HMMs, pairwise sequence alignment, and RNA folding we show how the TSP and the shortest Hamiltonian path problem can be implemented efficiently in the extended ADP framework. As a showcase application we investigate the ancient evolution of HOX gene clusters in terms of shortest Hamiltonian paths. Conclusions: The generalized ADP framework presented here greatly facilitates the development and implementation of dynamic programming algorithms for a wide spectrum of applications.

Seit W. Diffie und M. Hellman im Jahr 1976 ihren Ansatz für einen sicheren kryptographischen Schlüsselaustausch vorgestellten, ist der sogenannte Diskrete Logarithmus zu einem zentrales Thema der Kryptoanalyse geworden. Dieser stellt eine Erweiterung des bekannten Logarithmus auf beliebige endliche Gruppen dar. In der vorliegenden Dissertation werden zwei von C. Diem eingeführte Algorithmen untersucht, mit deren Hilfe der diskrete Logarithmus in der Picardgruppe glatter, nichthyperelliptischer Kurven vom Geschlecht g > 3 bzw. g > 4 über endlichen Körpern berechnet werden kann. Beide Ansätze basieren auf der sogenannten Indexkalkül-Methode und benutzen zur Erzeugung der dafür benötigten Relationen spezielle Linearsysteme, welche durch Schneiden von ebenen Modellen der Kurve mit Geraden erzeugt werden. Um Aussagen zur Laufzeit der Algorithmen tätigen zu können, werden verschiedene Sätze über die Geometrie von Kurven bewiesen. Als zentrale Aussage wird zum einem gezeigt, dass ebene Modelle niedrigen Grades effizient berechnet werden können. Zum anderen wird bewiesen, dass sich bei genügend großem Grundkörper die Anzahl der vollständig über dem Grundkörper zerfallenden Geraden wie heuristisch erwartet verhällt. Für beide Aussagen werden dabei Familien von Kurven betrachtet und diese gelten daher uniform für alle glatten, nichthyperelliptischen Kurven eines festen Geschlechts. Die genannten Resultate führen schlussendlich zu dem Beweis einer erwarteten Laufzeit von O(q^(2-2/(g-1))) für den ersten der beiden Algorithmen, wobei q die Anzahl der Elemente im Grundkörper darstellt. Der zweite Algoritmus verbessert dies auf eine heuristische Laufzeit in O(q^(2-2/(g-2))), imdem er Divisoren von höherem Spezialiätsgrad erzeugt. Es wird bewiesen, dass dieser Ansatz für einen uniform gegen 1 konvergierenden Anteil an glatten, nichthyperelliptischen Kurven eines festen Geschlechts über Grundkörpern großer Charakteristik eine große Anzahl an Relationen erzeugt. Wiederum werden zum Beweis der zugrundeliegenden geometrischen Aussagen Familien von Kurven betrachtet, um so die Uniformität zu gewährleisten. Beide Algorithmen wurden zudem implementiert. Zum Abschluss der Arbeit werden die Ergebnisse der entsprechenden Experimente vorgestellt und eingeordnet.

We study canonical forms for Hamiltonian and symplectic matrices or pencils under equivalence transformations which keep the class invariant. In contrast to other canonical forms our forms are as close as possible to a triangular structure in the same class. We give necessary and sufficient conditions for the existence of Hamiltonian and symplectic triangular Jordan, Kronecker and Schur forms. The presented results generalize results of Lin and Ho [17] and simplify the proofs presented there.

Inhalt der Dissertation ist der Einfluß, den die von Alfred Tarski formulierte mathematische Logik auf die Entstehung der drei Computerkonzepte des Konrad Zuse hatte.

We study numerical methods for finding the maximal symmetric positive definite solution of the nonlinear matrix equation $X = Q + LX^{-1}L^T$, where Q is symmetric positive definite and L is nonsingular. Such equations arise for instance in the analysis of stationary Gaussian reciprocal processes over a finite interval. Its unique largest positive definite solution coincides with the unique positive definite solution of a related discrete-time algebraic Riccati equation (DARE). We discuss how to use the butterfly SZ algorithm to solve the DARE. This approach is compared to several fixed point type iterative methods suggested in the literature.

Wir konstruieren Beispiele von Kontaktmannigfaltigkeiten in jeder ungeraden Dimension, welche endliche nicht-triviale algebraische Torsion (im Sinne von Latschev-Wendl) aufweisen, somit straff sind und keine starke symplektische Füllung haben. Wir beweisen, dass Giroux Torsion algebraische 1-Torsion in jeder ungeraden Dimension impliziert, womit eine Vermutung von Massot-Niederkrüger-Wendl bewiesen wird. Wir konstruieren unendlich viele nicht diffeomorphe Beispiele von 5-dimensionalen Kontaktmannigfaltigkeiten, welche straff sind, keine starke symplektische Füllung zulassen und keine Giroux Torsion haben. Wir erhalten Obstruktionen für symplektische Kobordismen, ohne für deren Beweis die SFT Maschinerie zu verwenden. Wir geben eine provisorische Definition eines spinalen offenen Buchs in höherer Dimension an, basierend auf der vom 3-dimensionalen Fall aus Lisi-van Horn Morris-Wendl. In einem Anhang geben wir in gemeinsamer Autorenschaft mit Richard Siefring eine wesentliche Zusammenfassung der Schnitttheorie für punktierte holomorphe Kurven und Hyperflächen an, welche die 3-dimensionalen Resultate von Siefring auf höhere Dimensionen verallgemeinert. Mittels der Schnitttheorie erhalten wir eine Anwendung für holomorphe Blätterungen von Kodimension zwei, die wir benutzen um das Verhalten von holomorphem Kurven in unseren Beispielen einzuschränken. / We construct examples in any odd dimension of contact manifolds with finite and non-zero algebraic torsion (in the sense of Latschev-Wendl), which are therefore tight and do not admit strong symplectic fillings. We prove that Giroux torsion implies algebraic 1-torsion in any odd dimension, which proves a conjecture of Massot-Niederkrüger-Wendl. We construct infinitely many non-diffeomorphic examples of 5-dimensional contact manifolds which are tight, admit no strong fillings, and do not have Giroux torsion. We obtain obstruction results for symplectic cobordisms, for which we give a proof not relying on SFT machinery. We give a tentative definition of a higher-dimensional spinal open book decomposition, based on the 3-dimensional one of Lisi-van Horn Morris-Wendl. An appendix written in co-authorship with Richard Siefring gives a basic outline of the intersection theory for punctured holomorphic curves and hypersurfaces, which generalizes his 3-dimensional results to higher dimensions. From the intersection theory we obtain an application to codimension-2 holomorphic foliations, which we use to restrict the behaviour of holomorphic curves in our examples.

We explore motivic homotopy theory over deeper bases than the spectrum of the integers: Starting from a commutative group object in a cartesian closed presentable infinity category, replacing the usual multiplicative group scheme in motivic spaces, we construct projective spaces, and show that infinite dimensional projective space is the classifying space of the group object. After passage to the stabilization, we construct a Snaith spectrum, calculate the cohomology represented by it for projective spaces and on its rationalization produce Adams operations and a splitting into summands of their eigenspaces.

This Ph.D. thesis deals with E1-ring structures on the Hermitian K-theory in the motivic setting, more precisely, the existence of such structures on the motivic spectrum representing the hermitianK-theory is proven. The presence of such structure is established through two different approaches. In both cases, we consider the category of algebraic vector bundles over a scheme, with the usual requirements to do motivic homotopy theory. This category has two natural symmetric monoidal structures given by the direct sum and the tensor product, together with a duality coming from the functor represented by the structural sheaf. The first symmetric monoidal structure is the one that we are going to group complete along this text, and we will see that the second one, the tensor product, is preserved giving rise to an E1-ring structure in the resulting spectrum. In the first case, a classic infinite loop space machine applies to the hermitian category of the category of algebraic vector bundles over a scheme. The second approach abords the construction using a new hermitian infinite loop space machine which uses the language of infinity categories. Both assemblies applied to our original category have like output a presheaf of E1-ring spectra. To get an spectrum representing the hermitian K-theory in the motivic context we need a motivic spectrum, i.e, a P1-spectrum. We use a delooping construction at the end of the text to obtain a presheaf of E1-ring P1-spectra from the two presheaves of E1-ring spectra indicated above.

In the thesis "On Boundaries of Statistical Models" problems related to a description of probability distributions with zeros, lying in the boundary of a statistical model, are treated. The distributions considered are joint distributions of finite collections of finite discrete random variables. Owing to this restriction, statistical models are subsets of finite dimensional real vector spaces. The support set problem for exponential families, the main class of models considered in the thesis, is to characterize the possible supports of distributions in the boundaries of these statistical models. It is shown that this problem is equivalent to a characterization of the face lattice of a convex polytope, called the convex support. The main tool for treating questions related to the boundary are implicit representations. Exponential families are shown to be sets of solutions of binomial equations, connected to an underlying combinatorial structure, called oriented matroid. Under an additional assumption these equations are polynomial and one is placed in the setting of commutative algebra and algebraic geometry. In this case one recovers results from algebraic statistics. The combinatorial theory of exponential families using oriented matroids makes the established connection between an exponential family and its convex support completely natural: Both are derived from the same oriented matroid. The second part of the thesis deals with hierarchical models, which are a special class of exponential families constructed from simplicial complexes. The main technical tool for their treatment in this thesis are so called elementary circuits. After their introduction, they are used to derive properties of the implicit representations of hierarchical models. Each elementary circuit gives an equation holding on the hierarchical model, and these equations are shown to be the "simplest", in the sense that the smallest degree among the equations corresponding to elementary circuits gives a lower bound on the degree of all equations characterizing the model. Translating this result back to polyhedral geometry yields a neighborliness property of marginal polytopes, the convex supports of hierarchical models. Elementary circuits of small support are related to independence statements holding between the random variables whose joint distributions the hierarchical model describes. Models for which the complete set of circuits consists of elementary circuits are shown to be described by totally unimodular matrices. The thesis also contains an analysis of the case of binary random variables. In this special situation, marginal polytopes can be represented as the convex hulls of linear codes. Among the results here is a classification of full-dimensional linear code polytopes in terms of their subgroups. If represented by polynomial equations, exponential families are the varieties of binomial prime ideals. The third part of the thesis describes tools to treat models defined by not necessarily prime binomial ideals. It follows from Eisenbud and Sturmfels'' results on binomial ideals that these models are unions of exponential families, and apart from solving the support set problem for each of these, one is faced with finding the decomposition. The thesis discusses algorithms for specialized treatment of binomial ideals, exploiting their combinatorial nature. The provided software package Binomials.m2 is shown to be able to compute very large primary decompositions, yielding a counterexample to a recent conjecture in algebraic statistics.

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.