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.

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.

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.

Improving cropping systems of semi-arid south-western Madagascar under multiple ecological and socio-economic constraints

Das Mahafaly Plateau im südwestlichen Madagaskar ist gekennzeichnet durch raue klimatische Bedingungen, vor allem regelmäßige Dürren und Trockenperioden, geringe Infrastruktur, steigende Unsicherheit, hohe Analphabetenrate und regelmäßige Zerstörung der Ernte durch Heuschreckenplagen. Da 97% der Bevölkerung von der Landwirtschaft abhängen, ist eine Steigerung der Produktivität von Anbausystemen die Grundlage für eine Verbesserung der Lebensbedingungen und Ernährungssicherheit in der Mahafaly Region. Da wenig über die Produktivität von traditionellen extensiven und neu eingeführten Anbaumethoden in diesem Gebiet bekannt ist, waren die Zielsetzungen der vorliegenden Arbeit, die limitierenden Faktoren und vielversprechende alternative Anbaumethoden zu identifizieren und diese unter Feldbedingungen zu testen. Wir untersuchten die Auswirkungen von lokalem Viehmist und Holzkohle auf die Erträge von Maniok, der Hauptanbaufrucht der Region, sowie die Beiträge von weiteren Faktoren, die im Untersuchungsgebiet ertragslimitierend sind. Darüber hinaus wurde in der Küstenregion das Potenzial für bewässerten Gemüseanbau mit Mist und Holzkohle untersucht, um zu einer Diversifizierung von Einkommen und Ernährung beizutragen. Ein weiterer Schwerpunkt dieser Arbeit war die Schätzung von Taubildung und deren Beitrag in der Jahreswasserbilanz durch Testen eines neu entworfenen Taumessgerätes. Maniok wurde über drei Jahre und in drei Versuchsfeldern in zwei Dörfern auf dem Plateau angebaut, mit applizierten Zeburindermistraten von 5 und 10 t ha-1, Holzkohleraten von 0,5 und 2 t ha-1 und Maniokpflanzdichten von 4500 Pflanzen ha-1. Maniokknollenerträge auf Kontrollflächen erreichten 1 bis 1,8 t Trockenmasse (TM) ha-1. Mist führte zu einer Knollenertragssteigerung um 30 - 40% nach drei Jahren in einem kontinuierlich bewirtschafteten Feld mit geringer Bodenfruchtbarkeit, hatte aber keinen Effekt auf den anderen Versuchsfeldern. Holzkohle hatte keinen Einfluss auf Erträge über den gesamten Testzeitraum, während die Infektion mit Cassava-Mosaikvirus zu Ertragseinbußen um bis zu 30% führte. Pflanzenbestände wurden felder-und jahresübergreifend um 4-54% des vollen Bestandes reduziert, was vermutlich auf das Auftreten von Trockenperioden und geringe Vitalität von Pflanzmaterial zurückzuführen ist. Karotten (Daucus carota L. var. Nantaise) und Zwiebeln (Allium cepa L. var. Red Créole) wurden über zwei Trockenzeiten mit lokal erhältlichem Saatgut angebaut. Wir testeten die Auswirkungen von lokalem Rindermist mit einer Rate von 40 t ha-1, Holzkohle mit einer Rate von 10 t ha-1, sowie Beschattung auf die Gemüseernteerträge. Lokale Bewässerungswasser hatte einen Salzgehalt von 7,65 mS cm-1. Karotten- und Zwiebelerträge über Behandlungen und Jahre erreichten 0,24 bis 2,56 t TM ha-1 beziehungsweise 0,30 bis 4,07 DM t ha-1. Mist und Holzkohle hatten keinen Einfluss auf die Erträge beider Kulturen. Beschattung verringerte Karottenerträge um 33% im ersten Jahr, während sich die Erträge im zweiten Jahr um 65% erhöhten. Zwiebelerträge wurden unter Beschattung um 148% und 208% im ersten und zweiten Jahr erhöht. Salines Bewässerungswasser sowie Qualität des lokal verfügbaren Saatgutes reduzierten die Keimungsraten deutlich. Taubildung im Küstendorf Efoetsy betrug 58,4 mm und repräsentierte damit 19% der Niederschlagsmenge innerhalb des gesamten Beobachtungszeitraum von 18 Monaten. Dies weist darauf hin, dass Tau in der Tat einen wichtigen Beitrag zur jährlichen Wasserbilanz darstellt. Tageshöchstwerte erreichten 0,48 mm. Die getestete Tauwaage-Vorrichtung war in der Lage, die nächtliche Taubildung auf der metallischen Kondensationsplatte zuverlässig zu bestimmen. Im abschließenden Kapitel werden die limitierenden Faktoren für eine nachhaltige Intensivierung der Landwirtschaft in der Untersuchungsregion diskutiert.