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.

Dipodal Ferrocene Derivatives for Nanostructured Redox-Functionalised Surfaces

Self-assembled monolayers (SAMs) on solid surfaces are of great current interest in science and nanotechnology. This thesis describes the preparation of several symmetrically 1,1’-substituted ferrocene derivatives that contain anchoring groups suitable for chemisorption on gold and may give rise to SAMs with electrochemically switchable properties. The binding groups are isocyano (-NC), isothiocyanato (-NCS), phosphanyl (-PPh2), thioether (-SR) and thienyl. In the context of SAM fabrication, isothiocyanates and phosphanes are adsorbate systems which, surprisingly, have remained essentially unexplored. SAMs on gold have been fabricated with the adsorbates from solution and investigated primarily by X-ray photoelectron spectroscopy and near-edge X-ray absorption fine structure spectroscopy. The results of these analytical investigations are presented and discussed in matters of the film quality and possible binding modes. The quality of self-assembled monolayers fabricated from 1,1’-diisocyanoferrocene and 1,1’-diisothiocyanatoferrocene turned out to be superior to that of films based on the other adsorbate species investigated. Films of those absorbates as well as of dppf afforded well-defined SAMs of good quality. All other films of this study based on sulfur containing anchoring groups exhibit chemical inhomogeneity and low orientational order of the film constituents and therefore failed to give rise to well-defined SAMs. Surface coordination chemistry is naturally related to molecular coordination chemistry. Since all SAMs described in this thesis were prepared on gold (111) surfaces, the ferrocene-based ligands of this study have been investigated in their ability for complexation towards gold(I). The sulfur-based ferrocene ligands [fc(SR)2] failed to give stable gold(I) complexes. In contrast, 1,1’-diisocyanoferrocene (1) proved to be an excellent ligand for the complexation of gold(I). Several complexes were prepared and characterised utilising a series of gold(I) acetylides. These complexes show interesting structural motifs in the solid state, since intramolecular aurophilic interactions lead to a parallel orientation of the isocyano moieties, combined with an antiparallel alignment of neighbouring units. The reaction of 1 with the gold(I) acetylide [Au(C≡C–Fc)]n turned out to be very unusual, since the two chemically equivalent isocyano groups undergo a different reaction. One group shows an ordinary coordination and the other one undergoes an extraordinary 1,1-insertion into the Au-C bond. As a sideline of the research of this thesis several ferrocene derivatives have been tested for their suitability for potential surface reactions. Copper(I) mediated 1,3-dipolar cycloadditions of azidoferrocene derivatives with terminal alkynes appeared very promising in this context, but failed to a certain extent in terms of ‘click’ chemistry, since the formation of the triazoles depended on the strict exclusion of oxygen and moisture and yields were only moderate. Staudinger reactions between dppf and azidoferrocene derivatives were also tested. The nucleophilic additions of secondary amines to 1,1’-diisothiocyanatoferrocene led to the respective thiourea derivatives in quantitative yields.

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.

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.

Development of hybrid UV VCSEL with organic active material and dielectric DBR mirrors for medical, sensoric and data storage applications

Lasers play an important role for medical, sensoric and data storage devices. This thesis is focused on design, technology development, fabrication and characterization of hybrid ultraviolet Vertical-Cavity Surface-Emitting Lasers (UV VCSEL) with organic laser-active material and inorganic distributed Bragg reflectors (DBR). Multilayer structures with different layer thicknesses, refractive indices and absorption coefficients of the inorganic materials were studied using theoretical model calculations. During the simulations the structure parameters such as materials and thicknesses have been varied. This procedure was repeated several times during the design optimization process including also the feedback from technology and characterization. Two types of VCSEL devices were investigated. The first is an index coupled structure consisting of bottom and top DBR dielectric mirrors. In the space in between them is the cavity, which includes active region and defines the spectral gain profile. In this configuration the maximum electrical field is concentrated in the cavity and can destroy the chemical structure of the active material. The second type of laser is a so called complex coupled VCSEL. In this structure the active material is placed not only in the cavity but also in parts of the DBR structure. The simulations show that such a distribution of the active material reduces the required pumping power for reaching lasing threshold. High efficiency is achieved by substituting the dielectric material with high refractive index for the periods closer to the cavity. The inorganic materials for the DBR mirrors have been deposited by Plasma- Enhanced Chemical Vapor Deposition (PECVD) and Dual Ion Beam Sputtering (DIBS) machines. Extended optimizations of the technological processes have been performed. All the processes are carried out in a clean room Class 1 and Class 10000. The optical properties and the thicknesses of the layers are measured in-situ by spectroscopic ellipsometry and spectroscopic reflectometry. The surface roughness is analyzed by atomic force microscopy (AFM) and images of the devices are taken with scanning electron microscope (SEM). The silicon dioxide (SiO2) and silicon nitride (Si3N4) layers deposited by the PECVD machine show defects of the material structure and have higher absorption in the ultra violet range compared to ion beam deposition (IBD). This results in low reflectivity of the DBR mirrors and also reduces the optical properties of the VCSEL devices. However PECVD has the advantage that the stress in the layers can be tuned and compensated, in contrast to IBD at the moment. A sputtering machine Ionsys 1000 produced by Roth&Rau company, is used for the deposition of silicon dioxide (SiO2), silicon nitride (Si3N4), aluminum oxide (Al2O3) and zirconium dioxide (ZrO2). The chamber is equipped with main (sputter) and assisted ion sources. The dielectric materials were optimized by introducing additional oxygen and nitrogen into the chamber. DBR mirrors with different material combinations were deposited. The measured optical properties of the fabricated multilayer structures show an excellent agreement with the results of theoretical model calculations. The layers deposited by puttering show high compressive stress. As an active region a novel organic material with spiro-linked molecules is used. Two different materials have been evaporated by utilizing a dye evaporation machine in the clean room of the department Makromolekulare Chemie und Molekulare Materialien (mmCmm). The Spiro-Octopus-1 organic material has a maximum emission at the wavelength λemission = 395 nm and the Spiro-Pphenal has a maximum emission at the wavelength λemission = 418 nm. Both of them have high refractive index and can be combined with low refractive index materials like silicon dioxide (SiO2). The sputtering method shows excellent optical quality of the deposited materials and high reflection of the multilayer structures. The bottom DBR mirrors for all VCSEL devices were deposited by the DIBS machine, whereas the top DBR mirror deposited either by PECVD or by combination of PECVD and DIBS. The fabricated VCSEL structures were optically pumped by nitrogen laser at wavelength λpumping = 337 nm. The emission was measured by spectrometer. A radiation of the VCSEL structure at wavelength 392 nm and 420 nm is observed.

CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions

We introduce a new mode of operation for CD-systems of restarting automata by providing explicit enable and disable conditions in the form of regular constraints. We show that, for each CD-system M of restarting automata and each mode m of operation considered by Messerschmidt and Otto, there exists a CD-system M' of restarting automata of the same type as M that, working in the new mode ed, accepts the language that M accepts in mode m. Further, we prove that in mode ed, a locally deterministic CD-system of restarting automata of type RR(W)(W) can be simulated by a locally deterministic CD-system of restarting automata of the more restricted type R(W)(W). This is the first time that a non-monotone type of R-automaton without auxiliary symbols is shown to be as expressive as the corresponding type of RR-automaton.

On CD-systems of stateless deterministic R-automata with window size one

We study cooperating distributed systems (CD-systems) of restarting automata that are very restricted: they are deterministic, they cannot rewrite, but only delete symbols, they restart immediately after performing a delete operation, they are stateless, and they have a read/write window of size 1 only, that is, these are stateless deterministic R(1)-automata. We study the expressive power of these systems by relating the class of languages that they accept by mode =1 computations to other well-studied language classes, showing in particular that this class only contains semi-linear languages, and that it includes all rational trace languages. In addition, we investigate the closure and non-closure properties of this class of languages and some of its algorithmic properties.

Synthese und Charakterisierung neuer symmetrischer und unsymmetrischer Spiro-p-oligophenyle

In der vorliegenden Arbeit wurden neue symmetrische Spiro-p-oligophenyle der allgemeinen Form Spiro-o-Φ[n,n] mit der Gesamtkettenlänge o=2n+2 Phenylringen (o > 10) und der Zahl n der Phenylringe in den p-Oligophenylsubstituenten am Spirobifluorenkern, dargestellt. Neben den symmetrischen Verbindungen wurden erstmals auch unsymmetrische Spiro-p-oligophenyle der allgemeinen Form Spiro-o-Φ[n,m] mit o=n+m+2 (o = 3-7) und n ≠ m synthetisiert. Aufgrund der sehr geringen Löslichkeit der größeren Verbindungen wurden löslichkeitssteigernde Substituenten an den endständigen Phenylringen angebracht. Bei den Verbindungen, die mit Trimethylsilyl-Gruppen (TMS-) in den endständigen meta-Positionen „3“ und „5“ substituiert wurden, konnte die Löslichkeit um mehrere Größenordnungen gesteigert werden, sodass die Darstellung der symmetrischen Verbindungen bis zu einer Kettenlänge von 16 Phenylringen möglich wurde. Nach erfolgreicher Synthese und Aufreinigung wurden die TMS-Gruppen wieder entfernt und die erhaltenen, unsubstituierten Verbindungen charakterisiert. Zusätzlich wurden auch die TMS-Derivate untersucht. Zur Charakterisierung zählten neben der Reinheits- und Strukturanalytik unter anderem auch spektroskopische (UV/Vis-Absorption, Fluoreszenz, Fluoreszenzquantenausbeute), elektrochemische (Cyclovoltammetrie) und thermische (Thermogravimetrie, Dynamische Differenzkalorimetrie) Untersuchungen. Hier wurde unter anderem der Einfluss der Kettenlänge und der Position der Spiroverknüpfung auf isomere Verbindungen gleicher Kettenlänge untersucht. Bei den spektroskopischen Messungen konnte eine Konvergenz der längstwelligen Absorptionsbanden, bzw. kürzestwelligen Fluoreszenzbanden mit zunehmender Kettenlänge beobachtet werden. Die effektive Konjugationslänge konnte so aus experimentellen Daten bestimmt werden zu 12 Phenylringen in der Absorption und 14 Phenylringen in der Fluoreszenz. Bei den Isomeren gleicher Kettenlänge zeigte sich in der Absorption eine hypsochrome Verschiebung der Absorptionsmaxima mit zunehmender Verschiebung der Spiroverknüpfung zum Kettenende hin, während die Position der Spiroverknüpfung keinen messbaren Einfluss auf die Verschiebung der Fluoreszenzbanden hatte. Die Substitution mit TMS in den meta-Positionen zeigte keinen messbaren Einfluss auf die Absorptions- bzw. Fluoreszenzbanden. Die elektrochemischen Untersuchungen zeigten mit zunehmender Kettenlänge eine erleichterte Oxidation und Reduktion, während bei Isomeren gleicher Kettenlänge die Oxidation mit Verschiebung der Spiroverknüpfung zum Kettenende hin erschwert und die Reduktion erleichtert war. Die thermogravimetrischen Analysen (TGA) zeigten eine außerordentlich hohe thermische Stabilität (5% Massenabnahme unter Schutzgas) der Spiro-p-oligophenyle von Td,5% = 474°C bei Spiro-5Φ[1,2] bis 570°C bei Spiro 8Φ[3,3]. Ebenso blieben hohe Rückstandsmassen unter Schutzgas bei 850°C zurück, wie das Beispiel Spiro 8Φ[3,3] mit 68% zeigt. Die Verbindungen zeigten hohe Schmelzpunkte (max. 496°C bei Spiro-6Φ[0,4]) und Glasübergangstemperaturen (max. 434°C bei p-TMS-Spiro-8Φ[3,3]). Viele der Verbindungen, besonders die in den meta-Positionen TMS-substituierten Verbindungen, bildeten stabile amorphe Gläser.

20. Theorietag der GI-Fachgruppe "Automaten und Formale Sprachen''

Die Fachgruppe AFS (früher Fachgruppe 0.1.5) der Gesellschaft für Informatik veranstaltet seit 1991 einmal im Jahr ein Treffen der Fachgruppe im Rahmen eines Theorietags, der traditionell eineinhalb Tage dauert. Seit dem Jahr 1996 wird dem eigentlichen Theorietag noch ein eintägiger Workshop zu speziellen Themen der theoretischen Informatik vorangestellt. In diesem Jahr wurde der Theorietag vom Fachgebiet "Theoretische Informatik" des Fachbereichs Elektrotechnik/Informatik der Universität Kassel organisiert. Er fand vom 29.9. bis 1.10.2010 in Baunatal bei Kassel statt. Dabei stand der begleitende Workshop unter dem allgemeinen Thema "Ausgewählte Themen der Theoretischen Informatik". Als Vortragende für diesen Workshop konnten Carsten Damm (Göttingen), Markus Holzer (Giessen), Peter Leupold (Kassel), Martin Plátek (Prag) und Heribert Vollmer (Hannover) gewonnen werden. Das Programm des eigentlichen Theorietags bestand aus 20 Vorträgen sowie der Sitzung der Fachgruppe AFS. In diesem Band finden sich die Zusammenfassungen aller Vorträge sowohl des Workshops als auch des Theorietags. Desweiteren enthält er das Programm und die Liste aller Teilnehmer.

CD-Systems of Stateless Deterministic R(1)-Automata Governed by an External Pushdown Store

We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed by an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of context-free trace languages.

On Globally Deterministic CD-Systems of Stateless R-Automata with Window Size One

It is known that cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 accept a class of semi-linear languages that properly includes all rational trace languages. Although the component automata of such a CD-system are all deterministic, in general the CD-system itself is not, as in each of its computations, the initial component and the successor components are still chosen nondeterministically. Here we study CD-systems of stateless deterministic restarting automata with window size 1 that are themselves completely deterministic. In fact, we consider two such types of CD-systems, the strictly deterministic systems and the globally deterministic systems.