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.

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.

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.

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.

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.

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.

Agroforestry systems of timber species and cacao: survival and growth during the early stages

In recent times, increased emphasis has been placed on diversifying the types of trees to shade cacao (Theobroma cacao L.) and to achieve additional services. Agroforestry systems that include profitable and native timber trees are a viable alternative but it is necessary to understand the growth characteristics of these species under different environmental conditions. Thus, timber tree species selection should be based on plant responses to biotic and abiotic factors. The aims of this study were (1) to evaluate growth rates and leaf area indices of the four commercial timber species: Cordia thaisiana, Cedrela odorata, Swietenia macrophylla and Tabebuia rosea in conjunction with incidence of insect attacks and (2) to compare growth rates of four Venezuelan Criollo cacao cultivars planted under the shade of these four timber species during the first 36 months after establishment. Parameters monitored in timber trees were: survival rates, growth rates expressed as height and diameter at breast height and leaf area index. In the four Cacao cultivars: height and basal diameter. C. thaisiana and C. odorata had the fastest growth and the highest survival rates. Growth rates of timber trees will depend on their susceptibility to insect attacks as well as to total leaf area. All cacao cultivars showed higher growth rates under the shade of C. odorata. Growth rates of timber trees and cacao cultivars suggest that combinations of cacao and timber trees are a feasible agroforestry strategy in Venezuela.

Effects of transformation processes in 'jubraka' agroforestry systems of the Nuba Mountains, Sudan, on nutrient fluxes

Intensification processes in homegardens of the Nuba Mountains, Sudan, raise concerns about strongly positive carbon (C) and nutrient balances which are expected to lead to substantial element losses from these agroecosystems, in particular via soil gaseous emissions. Therefore, this thesis aimed at the quantification of C, nitrogen (N), phosphorus (P) and potassium (K) input and output fluxes with a special focus on soil gaseous losses, and the calculation of respective element balances. A further focus in this thesis was rainfall, a valuable resource for rain-fed agriculture in the Nuba Mountains. To minimize negative consequences of the high variability of rainfall, risk reducing mechanisms were developed by rain-fed farmers that may lose their efficacy in the course of climate change effects predicted for East Africa. Therefore, the second objective of this study was to examine possible changes in rainfall amounts during the last 60 years and to provide reliable risk and probability statements of rainfall-induced events of agricultural importance to rain-fed farmers in the Nuba Mountains. Soil gaseous emissions of C (in form of CO2) and N (in form of NH3 and N2O) of two traditional and two intensified homegardens were determined with a portable dynamic closed chamber system. For C gaseous emission rates reached their peak at the onset of the rainy season (2,325 g CO2-C ha-1 h-1 in an intensified garden type) and for N during the rainy season (16 g NH3-N ha-1 h-1 and 11.3 g N2O-N ha-1 h-1, in a traditional garden type). Data indicated cumulative annual emissions of 5,893 kg CO2-C ha-1, 37 kg NH3-N ha-1, and 16 kg N2O-N ha-1. For the assessment of the long-term productivity of the two types of homegardens and the identification of pathways of substantial element losses, a C and nutrient budget approach was used. In three traditional and three intensified homegardens observation plots were selected. The following variables were quantified on each plot between June and December in 2010: soil amendments, irrigation, biomass removal, symbiotic N2 fixation, C fixation by photosynthesis, atmospheric wet and dry deposition, leaching and soil gaseous emissions. Annual balances for C and nutrients amounted to -21 kg C ha-1, -70 kg N ha-1, 9 kg P ha-1 and -117 kg K ha-1 in intensified homegardens and to -1,722 kg C ha-1, -167 kg N ha-1, -9 kg P ha-1 and -74 kg K ha-1 in traditional homegardens. For the analysis of rainfall data, the INSTAT+ software allowed to aggregate long-term daily rainfall records from the Kadugli and Rashad weather stations into daily, monthly and annual intervals and to calculate rainfall-induced events of agricultural importance. Subsequently, these calculated values and events were checked for possible monotonic trends by Mann-Kendall tests. Over the period from 1970 to 2009, annual rainfall did not change significantly for either station. However, during this period an increase of low rainfall events coinciding with a decline in the number of medium daily rainfall events was observed in Rashad. Furthermore, the availability of daily rainfall data enabled frequency and conditional probability calculations that showed either no statistically significant changes or trends resulting only in minor changes of probabilities.

Effects of transformation processes in 'jubraka' agroforestry systems of the Nuba Mountains, Sudan, on plant diversity

Deutsche Forschungsgemeinschaft