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.

Lithography-free micro- and nanostructuring based on conventional plasma etching

In now-a-days semiconductor and MEMS technologies the photolithography is the working horse for fabrication of functional devices. The conventional way (so called Top-Down approach) of microstructuring starts with photolithography, followed by patterning the structures using etching, especially dry etching. The requirements for smaller and hence faster devices lead to decrease of the feature size to the range of several nanometers. However, the production of devices in this scale range needs photolithography equipment, which must overcome the diffraction limit. Therefore, new photolithography techniques have been recently developed, but they are rather expensive and restricted to plane surfaces. Recently a new route has been presented - so-called Bottom-Up approach - where from a single atom or a molecule it is possible to obtain functional devices. This creates new field - Nanotechnology - where one speaks about structures with dimensions 1 - 100 nm, and which has the possibility to replace the conventional photolithography concerning its integral part - the self-assembly. However, this technique requires additional and special equipment and therefore is not yet widely applicable. This work presents a general scheme for the fabrication of silicon and silicon dioxide structures with lateral dimensions of less than 100 nm that avoids high-resolution photolithography processes. For the self-aligned formation of extremely small openings in silicon dioxide layers at in depth sharpened surface structures, the angle dependent etching rate distribution of silicon dioxide against plasma etching with a fluorocarbon gas (CHF3) was exploited. Subsequent anisotropic plasma etching of the silicon substrate material through the perforated silicon dioxide masking layer results in high aspect ratio trenches of approximately the same lateral dimensions. The latter can be reduced and precisely adjusted between 0 and 200 nm by thermal oxidation of the silicon structures owing to the volume expansion of silicon during the oxidation. On the basis of this a technology for the fabrication of SNOM calibration standards is presented. Additionally so-formed trenches were used as a template for CVD deposition of diamond resulting in high aspect ratio diamond knife. A lithography-free method for production of periodic and nonperiodic surface structures using the angular dependence of the etching rate is also presented. It combines the self-assembly of masking particles with the conventional plasma etching techniques known from microelectromechanical system technology. The method is generally applicable to bulk as well as layered materials. In this work, layers of glass spheres of different diameters were assembled on the sample surface forming a mask against plasma etching. Silicon surface structures with periodicity of 500 nm and feature dimensions of 20 nm were produced in this way. Thermal oxidation of the so structured silicon substrate offers the capability to vary the fill factor of the periodic structure owing to the volume expansion during oxidation but also to define silicon dioxide surface structures by selective plasma etching. Similar structures can be simply obtained by structuring silicon dioxide layers on silicon. The method offers a simple route for bridging the Nano- and Microtechnology and moreover, an uncomplicated way for photonic crystal fabrication.

Ein Beitrag zur realitätsnahen Modellierung und Analyse von stahlfaserverstärkten Stahlbeton- und Stahlbetonflächentragwerken

Das Werkstoffverhalten von stahlfaserfreiem bzw. stahlfaserverstärktem Stahlbeton unter biaxialle Druck- Zugbeanspruchung wurde experimentell und theoretisch untersucht. Die Basis der experimentellen Untersuchungen waren zahlreiche Versuche, die in der Vergangenheit an faserfreiem Stahlbetonscheiben zur Bestimmung des Werkstoffverhaltens von gerissenem Stahlbeton im ebenen Spannungszustand durchgeführt wurden. Bei diesen Untersuchungen wurde festgestellt, dass infolge einer Querzugbeanspruchung eine Abminderung der biaxialen Druckfestigkeit entsteht. Unter Berücksichtigung dieser Erkenntnisse sind zur Verbesserung der Werkstoffeigenschaften des Betons, Stahlbetonscheiben aus stahlfaserverstärktem Beton hergestellt worden. Die aus der Literatur bekannten Werkstoffmodelle für Beton sowie Stahlbeton, im ungerissenen und gerissenen Zustand wurden hinsichtlich der in der Vergangenheit ermittelten Materialeigenschaften des Betons bzw. Stahlbetons unter proportionalen sowie nichtproportionalen äußeren Belastungen erklärt und kritisch untersucht. In den frischen Beton wurden Stahlfasern hinzugegeben. Dadurch konnte die Festigkeits- und die Materialsteifigkeitsabminderung infolge Rissbildung, die zur Schädigung des Verbundwerkstoffs Beton führt, reduziert werden. Man konnte sehen, dass der Druckfestigkeitsabminderungsfaktor und insbesondere die zur maximal aufnehmbaren Zylinderdruckfestigkeit gehörende Stauchung, durch Zugabe von Stahlfasern besser begrenzt wird. Die experimentelle Untersuchungen wurden an sechs faserfreien und sieben stahlfaserverstärkten Stahlbetonscheiben unter Druck-Zugbelastung zur Bestimmung des Verhaltens des gerissenen faserfreien und stahlfaserverstärkten Stahlbetons durchgeführt. Die aus eigenen Versuchen ermittelten Materialeigenschaften des Betons, des stahlfaserverstärkten Betons und Stahlbetons im gerissenen Zustand wurden dargelegt und diskutiert. Bei der Rissbildung des quasi- spröden Werkstoffs Beton und dem stahlfaserverstärkten Beton wurde neben dem plastischen Fließen, auch die Abnahme des Elastizitätsmoduls festgestellt. Die Abminderung der aufnehmbaren Festigkeit und der zugehörigen Verzerrung lässt sich nicht mit der klassischen Fließtheorie der Plastizität ohne Modifizierung des Verfestigungsgesetzes erfassen. Es wurden auf elasto-plastischen Werkstoffmodellen basierende konstitutive Beziehungen für den faserfreien sowie den stahlfaserverstärkten Beton vorgeschlagen. Darüber hinaus wurde in der vorliegenden Arbeit eine auf dem elasto-plastischen Werkstoffmodell basierende konstitutive Beziehung für Beton und den stahlfaser-verstärkten Beton im gerissenen Zustand formuliert. Die formulierten Werkstoffmodelle wurden mittels dem in einer modularen Form aufgebauten nichtlinearen Finite Elemente Programm DIANA zu numerischen Untersuchungen an ausgewählten experimentell untersuchten Flächentragwerken, wie scheibenartigen-, plattenartigen- und Schalentragwerken aus faserfreiem sowie stahlfaserverstärktem Beton verwendet. Das entwickelte elasto-plastische Modell ermöglichte durch eine modifizierte effektive Spannungs-Verzerrungs-Beziehung für das Verfestigungsmodell, nicht nur die Erfassung des plastischen Fließens sondern auch die Berücksichtigung der Schädigung der Elastizitätsmodule infolge Mikrorissen sowie Makrorissen im Hauptzugspannungs-Hauptdruckspannungs-Bereich. Es wurde bei den numerischen Untersuchungen zur Ermittlung des Last-Verformungsverhaltens von scheibenartigen, plattenartigen- und Schalentragwerken aus faserfreiem und stahlfaserverstärktem Stahlbeton, im Vergleich mit den aus Versuchen ermittelten Ergebnissen, eine gute Übereinstimmung festgestellt.

Computation of locally free class groups

We show that the locally free class group of an order in a semisimple algebra over a number field is isomorphic to a certain ray class group. This description is then used to present an algorithm that computes the locally free class group. The algorithm is implemented in MAGMA for the case where the algebra is a group ring over the rational numbers.

On Alternating Non-Context-Free Grammars

We study several extensions of the notion of alternation from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. Thereby new grammatical characterizations are obtained for the class of languages that are accepted by alternating pushdown automata.

Computing Generators of Free Modules over Orders in Group Algebras

Let E be a number field and G be a finite group. Let A be any O_E-order of full rank in the group algebra E[G] and X be a (left) A-lattice. We give a necessary and sufficient condition for X to be free of given rank d over A. In the case that the Wedderburn decomposition E[G] \cong \oplus_xM_x is explicitly computable and each M_x is in fact a matrix ring over a field, this leads to an algorithm that either gives elements \alpha_1,...,\alpha_d \in X such that X = A\alpha_1 \oplus ... \oplusA\alpha_d or determines that no such elements exist. Let L/K be a finite Galois extension of number fields with Galois group G such that E is a subfield of K and put d = [K : E]. The algorithm can be applied to certain Galois modules that arise naturally in this situation. For example, one can take X to be O_L, the ring of algebraic integers of L, and A to be the associated order A(E[G];O_L) \subseteq E[G]. The application of the algorithm to this special situation is implemented in Magma under certain extra hypotheses when K = E = \IQ.

CD-Systems of Restarting Automata

Die vorliegende Arbeit behandelt Restartautomaten und Erweiterungen von Restartautomaten. Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt. Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole. Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird. Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten: CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt. Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren. Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen. Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben.