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.

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.

Untersuchungen zum Vorkommen und molekularen Mechanismus der Biofilm-Bildung bei Enterokokken aus verschiedenen klinischen Bereichen

Im Rahmen der vorliegenden Arbeit wurde eine größere Anzahl an E. faecalis Isolaten aus Vaginalabstrichen, erstmals insbesondere von Patientinnen, die an Bakterieller Vaginose litten, untersucht und mit E. faecalis Stämme aus verschiedenen anderen klinischen Bereichen auf das Vorkommen von Virulenzfaktoren verglichen. Weiterhin wurden Korrelationen zwischen bestimmten Faktoren und der Menge an produziertem Biofilm erstellt, um mögliche Zusammenhänge zum Mechanismus der Biofilm-Bildung zu erfassen. Mittels statistischer Analysen konnte hinsichtlich der 150 untersuchten E. faecalis Isolate nachgewiesen werden, dass keine signifikanten Unterschiede der Inzidenzen von Virulenzfaktoren (esp, asa1, gelE, GelE, cylA, β-Hämolyse) zwischen den Stämmen der verschiedenen Herkunftsbereiche bestanden. In Bezug auf das Auftreten von Biofilm-Bildung zeigte sich ein erhöhtes Vorkommen bei Stämmen aus Urin sowie invasiver Herkunft (insgesamt jeweils ca. 70 % mäßige und starke Biofilm-Bildner) im Vergleich zu E. faecalis Isolaten aus Wunden oder Faeces (je ca. 40 %). Statistische Auswertungen bzgl. des Zusammenhangs eines oder einer Kombination von Virulenzfaktoren mit der Menge an gebildetem Biofilm wiesen darauf hin, dass Isolate, die das esp Gen besaßen, in erhöhtem Maße zur Biofilm-Bildung befähigt waren. Dies zeigte einen gewissen Einfluss des Zellwandproteins auf die Fähigkeit zur Biofilm-Bildung bei E. faecalis. Allerdings wurden stets auch Stämme identifiziert, die die Fähigkeit zur Biofilm-Bildung trotz des Fehlens der jeweils untersuchten genetischen Determinante bzw. der Determinanten aufwiesen, so dass auf das Vorhandensein weiterer, unbekannter Einflussfaktoren auf den Mechanismus der Biofilm-Bildung bei E. faecalis geschlossen werden konnte. Unter 78 untersuchten E. faecium Isolaten aus verschiedenen klinischen Bereichen konnte lediglich ein Stamm (1,3 %) als mäßiger Biofilm-Bildner charakterisiert werden, so dass die Fähigkeit bei dieser Spezies in der hier untersuchten Region unter diesen Bedingungen kaum nachgewiesen werden konnte. Einen Schwerpunkt dieser Arbeit bildete die Untersuchung zum Vorkommen von Virulenzfaktoren und Biofilm-Bildung bei E. faecalis Isolaten aus Vaginalabstrichen. Bzgl. des Auftretens von Virulenzfaktoren und Biofilm-Produktion konnte kein Unterschied zwischen Stämmen assoziiert mit Bakterieller Vaginose und Isolaten einer Vergleichsgruppe festgestellt werden. Allerdings zeigte eine Gegenüberstellung mit den untersuchten E. faecalis Stämmen aus anderen klinischen Bereichen, dass die 80 Isolate aus Vaginalabstrichen eine ähnlich hohe Inzidenz bestimmter Virulenzfaktoren wie Stämme aus Faeces, Urin, Wunden oder invasiver Herkunft sowie eine mit den Isolaten aus Urin und invasiver Herkunft vergleichbar hohe Fähigkeit zur Biofilm-Bildung aufwiesen (ca. 75 % mäßige und starke Biofilm-Bildner). Dies deutete auf eine Verbreitung der Biofilm-Bildungsfähigkeit bei E. faecalis Stämmen der Vaginalflora und somit auf eine große Bedeutung der Eigenschaft für Isolate dieser Herkunft hin. Die statistische Auswertung der Korrelationen von Virulenzfaktoren mit der Menge an gebildetem Biofilm lieferte ähnliche Ergebnisse wie die Analysen bzgl. der 150 E. faecalis Isolate aus anderen klinischen Bereichen und untermauerte die Annahme, dass zusätzliche Faktoren zu den hier untersuchten Determinanten bei E. faecalis vorhanden sein müssen, die Einfluss auf den Mechanismus der Biofilm-Bildung nehmen. Deshalb konzentrierte sich ein weiterer Teil der vorliegenden Arbeit auf die Herstellung und Charakterisierung von E. faecalis Biofilm-Spontanmutanten, um bisher noch ungeklärte Mechanismen oder neue Faktoren zu erkennen, die Einfluss auf die Biofilm-Bildung bei E. faecalis nehmen. Die Untersuchung einer Mutante (1.10.16) und ihres Wildtypstamms lieferte erstmals den phänotypischen Nachweis des HMW-Komplexes der drei Bee-Proteine sowie die Identifizierung konservierter Pili-Motive dieser Proteine. Des Weiteren schien die in diesem Cluster ebenfalls codierte Sortase-1 dasjenige Enzym zu sein, das höchstwahrscheinlich die Bindung des Proteins Bee-2 innerhalb dieses HMW-Komplexes katalysiert. Insofern lieferten diese Untersuchungen neue, konkrete Hinweise zur Rolle des bee Genclusters bei der Pili-Biogenese und Biofilm-Bildung von E. faecalis. Darüber hinaus stellen Erkenntnisse aus der Charakterisierung von zwei weiteren hergestellten Biofilm-Spontanmutanten viel versprechende Ausgangspunkte für zukünftige Untersuchungen dar, die ein weitergehendes Verständnis der molekularen Mechanismen der Biofilm-Bildung bei E. faecalis erzielen könnten.

Heat stress response for physiological traits in dairy and dual purpose cattle populations on phenotypic and genetic scales

The main objective of this thesis was to determine the potential impact of heat stress (HS) on physiological traits of lactating cows and semen quality of bulls kept in a temperate climate. The thesis is comprised of three studies. An innovative statistical modeling aspect common to all three studies was the application of random regression methodology (RRM) to study the phenotypic and genetic trajectory of traits in dependency of a continuous temperature humidity index (THI). In the first study, semen quality and quantity traits of 562 Holstein sires kept on an AI station in northwestern Germany were analyzed in the course of THI calculated from data obtained from the nearest weather station. Heat stress was identified based on a decline in semen quality and quantity parameters. The identified general HS threshold (THI = 60) and the thermoneutal zone (THI in the range from 50 to 60) for semen production were lower than detected in studies conducted in tropical and subtropical climates. Even though adult bulls were characterized by higher semen productivity compared to younger bulls, they responded with a stronger semen production loss during harsh environments. Heritabilities (low to moderate range) and additive genetic variances of semen characteristics varied with different levels of THI. Also, based on genetic correlations genotype, by environment interactions were detected. Taken together, these findings suggest the application of specific selection strategies for specific climate conditions. In the second study, the effect of the continuous environmental descriptor THI as measured inside the barns on rectal temperatures (RT), skin temperatures (ST), vaginal temperatures (VT), respiration rates (RR), and pulse rate (PR) of lactating Holstein Friesian (HF) and dual-purpose German black pied cattle (DSN) was analyzed. Increasing HS from THI 65 (threshold) to THI 86 (maximal THI) resulted in an increase of RT by 0.6 °C (DSN) and 1 °C (HF), ST by 3.5 °C (HF) and 8 °C (DSN), VT by 0.3 °C (DSN), and RR by 47 breaths / minute (DSN), and decreased PR by 7 beats / minute (DSN). The undesired effects of rising THI on physiological traits were most pronounced for cows with high levels of milk yield and milk constituents, cows in early days in milk and later parities, and during summer seasons in the year 2014. In the third study of this dissertation, the genetic components of the cow’s physiological responses to HS were investigated. Heat stress was deduced from indoor THI measurements, and physiological traits were recorded on native DSN cows and their genetically upgraded crosses with Holstein Friesian sires in two experimental herds from pasture-based production systems reflecting a harsh environment of the northern part of Germany. Although heritabilities were in a low range (from 0.018 to 0.072), alterations of heritabilities, repeatabilities, and genetic components in the course of THI justify the implementation of genetic evaluations including heat stress components. However, low repeatabilities indicate the necessity of using repeated records for measuring physiological traits in German cattle. Moderate EBV correlations between different trait combinations indicate the potential of selection for one trait to simultaneously improve the other physiological attributes. In conclusion, bulls of AI centers and lactating cows suffer from HS during more extreme weather conditions also in the temperate climate of Northern Germany. Monitoring physiological traits during warm and humid conditions could provide precious information for detection of appropriate times for implementation of cooling systems and changes in feeding and management strategies. Subsequently, the inclusion of these physiological traits with THI specific breeding values into overall breeding goals could contribute to improving cattle adaptability by selecting the optimal animal for extreme hot and humid conditions. Furthermore, the recording of meteorological data in close distance to the cow and visualizing the surface body temperature by infrared thermography techniques might be helpful for recognizing heat tolerance and adaptability in cattle.