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.

Degrees of Free Word-Order and Freely Rewriting Restarting Automata

In natural languages with a high degree of word-order freedom syntactic phenomena like dependencies (subordinations) or valencies do not depend on the word-order (or on the individual positions of the individual words). This means that some permutations of sentences of these languages are in some (important) sense syntactically equivalent. Here we study this phenomenon in a formal way. Various types of j-monotonicity for restarting automata can serve as parameters for the degree of word-order freedom and for the complexity of word-order in sentences (languages). Here we combine two types of parameters on computations of restarting automata: 1. the degree of j-monotonicity, and 2. the number of rewrites per cycle. We study these notions formally in order to obtain an adequate tool for modelling and comparing formal descriptions of (natural) languages with different degrees of word-order freedom and word-order complexity.

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.

Shrinking restarting automata

Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

On the Descriptional Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. We focus on the descriptional complexity of these automata, establishing two complexity measures that are both based on the description of t-sRL-automata in terms of so-called meta-instructions. We present some hierarchy results as well as a non-recursive trade-off between deterministic 2-sRL-automata and finite-state acceptors.

The Degree of Word-Expansion of Lexicalized RRWW-Automata

Restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. We study a measure for the degree of nondeterminism of (context-free) languages in terms of deterministic restarting automata that are (strongly) lexicalized. This measure is based on the number of auxiliary symbols (categories) used for recognizing a language as the projection of its characteristic language onto its input alphabet. This type of recognition is typical for analysis by reduction, a method used in linguistics for the creation and verification of formal descriptions of natural languages. Our main results establish a hierarchy of classes of context-free languages and two hierarchies of classes of non-context-free languages that are based on the expansion factor of a language.

On Vessiot's Theory of Partial Differential Equations

The object of research presented here is Vessiot's theory of partial differential equations: for a given differential equation one constructs a distribution both tangential to the differential equation and contained within the contact distribution of the jet bundle. Then within it, one seeks n-dimensional subdistributions which are transversal to the base manifold, the integral distributions. These consist of integral elements, and these again shall be adapted so that they make a subdistribution which closes under the Lie-bracket. This then is called a flat Vessiot connection. Solutions to the differential equation may be regarded as integral manifolds of these distributions. In the first part of the thesis, I give a survey of the present state of the formal theory of partial differential equations: one regards differential equations as fibred submanifolds in a suitable jet bundle and considers formal integrability and the stronger notion of involutivity of differential equations for analyzing their solvability. An arbitrary system may (locally) be represented in reduced Cartan normal form. This leads to a natural description of its geometric symbol. The Vessiot distribution now can be split into the direct sum of the symbol and a horizontal complement (which is not unique). The n-dimensional subdistributions which close under the Lie bracket and are transversal to the base manifold are the sought tangential approximations for the solutions of the differential equation. It is now possible to show their existence by analyzing the structure equations. Vessiot's theory is now based on a rigorous foundation. Furthermore, the relation between Vessiot's approach and the crucial notions of the formal theory (like formal integrability and involutivity of differential equations) is clarified. The possible obstructions to involution of a differential equation are deduced explicitly. In the second part of the thesis it is shown that Vessiot's approach for the construction of the wanted distributions step by step succeeds if, and only if, the given system is involutive. Firstly, an existence theorem for integral distributions is proven. Then an existence theorem for flat Vessiot connections is shown. The differential-geometric structure of the basic systems is analyzed and simplified, as compared to those of other approaches, in particular the structure equations which are considered for the proofs of the existence theorems: here, they are a set of linear equations and an involutive system of differential equations. The definition of integral elements given here links Vessiot theory and the dual Cartan-Kähler theory of exterior systems. The analysis of the structure equations not only yields theoretical insight but also produces an algorithm which can be used to derive the coefficients of the vector fields, which span the integral distributions, explicitly. Therefore implementing the algorithm in the computer algebra system MuPAD now is possible.

Theory for the Photoacoustic Response to X-Ray Absorption

A microscopic theory is presented for the photoacoustic effect induced in solids by x-ray absorption. The photoacoustic effect results from the thermalization of the excited Auger electrons and photoelectrons. We explain the dependence of the photoacoustic signal S on photon energy and the proportionality to the x-ray absorption coefficient in agreement with recent experiments on Cu. Results are presented for the dependence of S on photon energy, sample thickness, and the electronic structure of the absorbing solid.

Theory for Optical Absorption in Small Clusters: Dependence on Atomic Structure and Cluster Size

We present a theory which permits for the first time a detailed analysis of the dependence of the absorption spectrum on atomic structure and cluster size. Thus, we determine the development of the collective excitations in small clusters and show that their broadening depends sensitively on the tomic structure, in particular at the surface. Results for Hg_n^+ clusters show that the plasmon energy is close to its jellium value in the case of spherical-like structures, but is in general between w_p/ \wurzel{3} and w_p/ \wurzel{2} for compact clusters. A particular success of our theory is the identification of the excitations contributing to the absorption peaks.

Theory for the optical properties of small Hg_n clusters

The static and dynamical polarizabilities of the Hg-dimer are calculated by using a Hubbard Hamiltonian to describe the electronic structure. The Hamiltonian is diagonalized exactly within a subspace of second-quantized electronic states from which only multiply ionized atomic configurations have been excluded. With this approximation we can describe the most important electronic transitions including the effect of charge fluctuations. We analyze the polarizability as a function of the intraatomic Coulomb interaction which represents the repulsion between electrons. We obtain that this interaction results in strong electronic correlations in the excited states and increases the first excitation energy of the dimer by 0.8 eV in comparison to a calculation which neglects correlations, resulting in a better agreement with the experiment.

Theory for the change of bond character in divalent-metal clusters

To determine the size dependence of the bonding in divalent-metal clusters we use a many-electron Hamiltonian describing the interplay between van der Waals (vdW) and covalent interactions. Using a saddle-point slave-boson method and taking into account the size-dependent screening of charge fluctuations, we obtain for Hg_n a sharp transition from vdW to covalent bonding for increasing n. We show also, by solving the model Hamiltonian exactly, that for divalent metals vdW and covalent bonding coexist already in the dimers.

Photoionization of Kr near 4s threshold: II. Intermediate-coupling theory

The Kr 4s-electron photoionization cross section as a function of the exciting-photon energy in the range between 30 eV and 90 eV was calculated using the configuration interaction (CI) technique in intermediate coupling. In the calculations the 4p spin-orbital interaction and corrections due to higher orders of perturbation theory (the so-called Coulomb interaction correlational decrease) were considered. Energies of Kr II states were calculated and agree with spectroscopic data within less than 10 meV. For some of the Kr II states new assignments were suggested on the basis of the largest component among the calculated CI wavefunctions.