Restarting automata with restricted utilization of auxiliary symbols

The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

Asymptotics of number fields and the Cohen-Lenstra heuristics

We study the asymptotics conjecture of Malle for dihedral groups Dl of order 2l, where l is an odd prime. We prove the expected lower bound for those groups. For the upper bounds we show that there is a connection to class groups of quadratic number fields. The asymptotic behavior of those class groups is predicted by the Cohen-Lenstra heuristics. Under the assumption of this heuristic we are able to prove the expected upper bounds.

Die aeroelastische Stabilitätsanalyse – ein praxisnaher Ansatz zur intervalltheoretischen Betrachtung von Modellierungsunsicherheiten am Flugzeug

Die Untersuchung des dynamischen aeroelastischen Stabilitätsverhaltens von Flugzeugen erfordert sehr komplexe Rechenmodelle, welche die wesentlichen elastomechanischen und instationären aerodynamischen Eigenschaften der Konstruktion wiedergeben sollen. Bei der Modellbildung müssen einerseits Vereinfachungen und Idealisierungen im Rahmen der Anwendung der Finite Elemente Methode und der aerodynamischen Theorie vorgenommen werden, deren Auswirkungen auf das Simulationsergebnis zu bewerten sind. Andererseits können die strukturdynamischen Kenngrößen durch den Standschwingungsversuch identifiziert werden, wobei die Ergebnisse Messungenauigkeiten enthalten. Für eine robuste Flatteruntersuchung müssen die identifizierten Unwägbarkeiten in allen Prozessschritten über die Festlegung von unteren und oberen Schranken konservativ ermittelt werden, um für alle Flugzustände eine ausreichende Flatterstabilität sicherzustellen. Zu diesem Zweck wird in der vorliegenden Arbeit ein Rechenverfahren entwickelt, welches die klassische Flatteranalyse mit den Methoden der Fuzzy- und Intervallarithmetik verbindet. Dabei werden die Flatterbewegungsgleichungen als parameterabhängiges nichtlineares Eigenwertproblem formuliert. Die Änderung der komplexen Eigenlösung infolge eines veränderlichen Einflussparameters wird mit der Methode der numerischen Fortsetzung ausgehend von der nominalen Startlösung verfolgt. Ein modifizierter Newton-Iterations-Algorithmus kommt zur Anwendung. Als Ergebnis liegen die berechneten aeroelastischen Dämpfungs- und Frequenzverläufe in Abhängigkeit von der Fluggeschwindigkeit mit Unschärfebändern vor.

Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata

The nonforgetting restarting automaton is a generalization of the restarting automaton that, when executing a restart operation, changes its internal state based on the current state and the actual contents of its read/write window instead of resetting it to the initial state. Another generalization of the restarting automaton is the cooperating distributed system (CD-system) of restarting automata. Here a finite system of restarting automata works together in analyzing a given sentence, where they interact based on a given mode of operation. As it turned out, CD-systems of restarting automata of some type X working in mode =1 are just as expressive as nonforgetting restarting automata of the same type X. Further, various types of determinism have been introduced for CD-systems of restarting automata called strict determinism, global determinism, and local determinism, and it has been shown that globally deterministic CD-systems working in mode =1 correspond to deterministic nonforgetting restarting automata. Here we derive some lower bound results for some types of nonforgetting restarting automata and for some types of CD-systems of restarting automata. In this way we establish separations between the corresponding language classes, thus providing detailed technical proofs for some of the separation results announced in the literature.

3D Simultaneous Inversion for Seismic Structure and Local Hypocenters in Germany under Consideration of Seismic Anisotropy in the Upper Mantel

The main task of this work has been to investigate the effects of anisotropy onto the propagation of seismic waves along the Upper Mantle below Germany and adjacent areas. Refraction- and reflexion seismic experiments proved the existence of Upper Mantle anisotropy and its influence onto the propagation of Pn-waves. By the 3D tomographic investigations that have been done here for the crust and the upper mantle, considering the influence of anisotropy, a gap for the investigations in Europe has been closed. These investigations have been done with the SSH-Inversionprogram of Prof. Dr. M. Koch, which is able to compute simultaneously the seismic structure and hypocenters. For the investigation, a dataset has been available with recordings between the years 1975 to 2003 with a total of 60249 P- and 54212 S-phase records of 10028 seismic events. At the beginning, a precise analysis of the residuals (RES, the difference between calculated and observed arrivaltime) has been done which confirmed the existence of anisotropy for Pn-phases. The recognized sinusoidal distribution has been compensated by an extension of the SSH-program by an ellipse with a slow and rectangular fast axis with azimuth to correct the Pn-velocities. The azimuth of the fast axis has been fixed by the application of the simultaneous inversion at 25° - 27° with a variation of the velocities at +- 2.5 about an average value at 8 km/s. This new value differs from the old one at 35°, recognized in the initial residual analysis. This depends on the new computed hypocenters together with the structure. The application of the elliptical correction has resulted in a better fit of the vertical layered 1D-Model, compared to the results of preceding seismological experiments and 1D and 2D investigations. The optimal result of the 1D-inversion has been used as initial starting model for the 3D-inversions to compute the three dimensional picture of the seismic structure of the Crust and Upper Mantle. The simultaneous inversion has showed an optimization of the relocalization of the hypocenters and the reconstruction of the seismic structure in comparison to the geology and tectonic, as described by other investigations. The investigations for the seismic structure and the relocalization have been confirmed by several different tests. First, synthetic traveltime data are computed with an anisotropic variation and inverted with and without anisotropic correction. Further, tests with randomly disturbed hypocenters and traveltime data have been proceeded to verify the influence of the initial values onto the relocalization accuracy and onto the seismic structure and to test for a further improvement by the application of the anisotropic correction. Finally, the results of the work have been applied onto the Waldkirch earthquake in 2004 to compare the isotropic and the anisotropic relocalization with the initial optimal one to verify whether there is some improvement.

Root parametrized differential equations

The present thesis is about the inverse problem in differential Galois Theory. Given a differential field, the inverse  problem asks which linear algebraic groups can be realized as differential Galois groups of Picard-Vessiot extensions of this field.   In this thesis we will concentrate on the realization of the classical groups as differential Galois groups. We introduce a method for a very general realization of these groups. This means that we present for the classical groups of Lie rank $l$ explicit linear differential equations where the coefficients are differential polynomials in $l$ differential indeterminates over an algebraically closed field of constants $C$, i.e. our differential ground field is purely differential transcendental over the constants.   For the groups of type $A_l$, $B_l$, $C_l$, $D_l$ and $G_2$ we managed to do these realizations at the same time in terms of Abhyankar's program 'Nice Equations for Nice Groups'. Here the choice of the defining matrix is important. We found out that an educated choice of $l$ negative roots for the parametrization together with the positive simple roots leads to a nice differential equation and at the same time defines a sufficiently general element of the Lie algebra. Unfortunately for the groups of type $F_4$ and $E_6$ the linear differential equations for such elements are of enormous length. Therefore we keep in the case of $F_4$ and $E_6$ the defining matrix differential equation which has also an easy and nice shape.   The basic idea for the realization is the application of an upper and lower bound criterion for the differential Galois group to our parameter equations and to show that both bounds coincide. An upper and lower bound criterion can be found in literature. Here we will only use the upper bound, since for the application of the lower bound criterion an important condition has to be satisfied. If the differential ground field is $C_1$, e.g., $C(z)$ with standard derivation, this condition is automatically satisfied. Since our differential ground field is purely differential transcendental over $C$, we have no information whether this condition holds or not.   The main part of this thesis is the development of an alternative lower bound criterion and its application. We introduce the specialization bound. It states that the differential Galois group of a specialization of the parameter equation is contained in the differential Galois group of the parameter equation. Thus for its application we need a differential equation over $C(z)$ with given differential Galois group. A modification of a result from Mitschi and Singer yields such an equation over $C(z)$ up to differential conjugation, i.e. up to transformation to the required shape. The transformation of their equation to a specialization of our parameter equation is done for each of the above groups in the respective transformation lemma.

Downscaling and Modeling the Effects of Climate Change on Hydrology and Water Resources in the Upper Blue Nile River Basin, Ethiopia

The Upper Blue Nile River Basin (UBNRB) located in the western part of Ethiopia, between 7° 45’ and 12° 45’N and 34° 05’ and 39° 45’E has a total area of 174962 km2 . More than 80% of the population in the basin is engaged in agricultural activities. Because of the particularly dry climate in the basin, likewise to most other regions of Ethiopia, the agricultural productivity depends to a very large extent on the occurrence of the seasonal rains. This situation makes agriculture highly vulnerable to the impact of potential climate hazards which are about to inflict Africa as a whole and Ethiopia in particular. To analyze these possible impacts of future climate change on the water resources in the UBNRB, in the first part of the thesis climate projection for precipitation, minimum and maximum temperatures in the basin, using downscaled predictors from three GCMs (ECHAM5, GFDL21 and CSIRO-MK3) under SRES scenarios A1B and A2 have been carried out. The two statistical downscaling models used are SDSM and LARS-WG, whereby SDSM is used to downscale ECHAM5-predictors alone and LARS-WG is applied in both mono-model mode with predictors from ECHAM5 and in multi-model mode with combined predictors from ECHAM5, GFDL21 and CSIRO-MK3. For the calibration/validation of the downscaled models, observed as well as NCEP climate data in the 1970 - 2000 reference period is used. The future projections are made for two time periods; 2046-2065 (2050s) and 2081-2100 (2090s). For the 2050s future time period the downscaled climate predictions indicate rise of 0.6°C to 2.7°C for the seasonal maximum temperatures Tmax, and of 0.5°C to 2.44°C for the minimum temperatures Tmin. Similarly, during the 2090s the seasonal Tmax increases by 0.9°C to 4.63°C and Tmin by 1°C to 4.6°C, whereby these increases are generally higher for the A2 than for the A1B scenario. For most sub-basins of the UBNRB, the predicted changes of Tmin are larger than those of Tmax. Meanwhile, for the precipitation, both downscaling tools predict large changes which, depending on the GCM employed, are such that the spring and summer seasons will be experiencing decreases between -36% to 1% and the autumn and winter seasons an increase of -8% to 126% for the two future time periods, regardless of the SRES scenario used. In the second part of the thesis the semi-distributed, physically based hydrologic model, SWAT (Soil Water Assessment Tool), is used to evaluate the impacts of the above-predicted future climate change on the hydrology and water resources of the UBNRB. Hereby the downscaled future predictors are used as input in the SWAT model to predict streamflow of the Upper Blue Nile as well as other relevant water resources parameter in the basin. Calibration and validation of the streamflow model is done again on 1970-2000 measured discharge at the outlet gage station Eldiem, whereby the most sensitive out the numerous “tuneable” calibration parameters in SWAT have been selected by means of a sophisticated sensitivity analysis. Consequently, a good calibration/validation model performance with a high NSE-coefficient of 0.89 is obtained. The results of the future simulations of streamflow in the basin, using both SDSM- and LARS-WG downscaled output in SWAT reveal a decline of -10% to -61% of the future Blue Nile streamflow, And, expectedly, these obviously adverse effects on the future UBNRB-water availibiliy are more exacerbated for the 2090’s than for the 2050’s, regardless of the SRES.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.