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.

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.