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.

Segregation unter Stagnationsbedingungen

Anlass der Untersuchung sind Verstärkungen von strukturwandel- und globalisierungsbedingten Wandlungen unter Schrumpfungs- und Stagnationsbedingungen. Denn Stagnations- und Schrumpfungstendenzen in einer Region sind selektiv, sie begünstigen über verschiedene Mechanismen Polarisierungen und Marginalisierungen: Die allgemeine Entspannung am Wohnungsmarkt hat erhöhte Mobilität und damit sozialräumliche Segregierungen und Polarisierungen der Wohnungsversorgung zur Folge. Leerstände und ausbleibende Investitionen begünstigen Polarisierungen von baulich-räumlichen Qualitäten. Diese beiden Entwicklungen überlagern sich im Stadtraum und verstärken sich gegenseitig. Dabei verbessert sich die Wohnungsversorgung in den benachteiligten Quartieren kaum, so die Ausgangshypothesen. Die Untersuchung fragt nach den Wirkungen des Nebeneinanders von Wachstums-, Stagnations- und Schrumpfungserscheinungen auf unterschiedlichen Maßstabsebenen, dem Zusammenspiel von sozialstrukturellen und qualitativen Veränderungen der baulich-räumlichen Gegebenheiten in den Quartieren sowie in innerstädtischer Differenzierung. Dabei interessieren besonders die Einflüsse eines regional entspannten Wohnungsmarktes und dessen Folgen für die Verwertungsstrategien im Wohnungsbestand auf Segregationsprozesse und die Wohnungsversorgung. Als Fallbeispiel der Untersuchung dient die Stadt Kassel. Der sozialräumliche Fokus liegt auf drei Typen benachteiligter Quartiere: Neben den in der aktuellen Diskussion zumeist betrachteten gründerzeitlichen Arbeiterquartieren und den Großsiedlungen der 1960/70er Jahre wurden auch die peripheren Geschosswohnungsbausiedlungen der 1950er/60er Jahre in die Untersuchung einbezogen, um den unterschiedlichen Rahmenbedingungen und Wirkungen in den Quartierstypen auf die Spur zu kommen und damit letztlich Grundlagen für stadtentwicklungspolitische Strategien zu erarbeiten. Die kleinräumigen Analysen von sozialräumlicher und baulich-räumlicher Struktur sowie zur Wohnungsversorgung deckten Parallelen und gegenläufige Entwicklungen zwischen den unterschiedlichen Quartierstypen auf; es ergaben sich verschiedene Anhaltspunkte zur Erhärtung der Ausgangsthesen. So wurde z.B. deutlich, dass sich unter den Marktbedingungen stagnierender Städte die Wohnflächenversorgung in den benachteiligten Quartieren kaum verbessert. Hierin zeigt sich ein entscheidender Unterschied zu stark schrumpfenden Städten, in denen sich die Versorgungslage (fast) durchgängig verbessert. Wohnungsmarktbarrieren wirken offensichtlich unter Stagnationsbedingungen für bestimmte Bevölkerungsgruppen weiter. Da sich ihre Wirkung aber für weitere Kreise der Bevölkerung abschwächt, verschärfen sich sozialräumliche Konzentrationen. Vor allem aber wurden Überlagerung und gegenseitige Verstärkung dieser sozialräumlichen mit baulich-räumlichen Polarisierungen deutlich, die vor allem aus stadträumlich konzentrierten Investitionen in den Gebäude- und Wohnungsbestand resultieren. Letztlich zeigt sich damit, dass regulierende Eingriffe nicht nur im Rahmen des Umbaus und der Erneuerung der Quartiere erforderlich sind, sondern insbesondere auch in den Wohnungsmarkt und dies auch bei entspannter regionaler Marktlage. Andernfalls ist weder eine angemessene Wohnungsversorgung aller Bevölkerungsgruppen noch der Zusammenhalt der Stadt(Gesellschaft) zu gewährleisten. Dabei ist die Stadtpolitik permanent mit der Gleichzeitigkeit von (wirtschaftlicher) Standortpolitik und sozialer Stadtentwicklung konfrontiert, die sie im Sinne einer nachhaltigen Entwicklung gegeneinander und miteinander abwägen muss.

Digital image analysis as a tool to estimate legume contributions in legume-grass swards

Summary: Productivity and forage quality of legume-grass swards are important factors for successful arable farming in both organic and conventional farming systems. For these objectives the botanical composition of the swards is of particular importance, especially, the content of legumes due to their ability to fix airborne nitrogen. As it can vary considerably within a field, a non-destructive detection method while doing other tasks would facilitate a more targeted sward management and could predict the nitrogen supply of the soil for the subsequent crop. This study was undertaken to explore the potential of digital image analysis (DIA) for a non destructive prediction of legume dry matter (DM) contribution of legume-grass mixtures. For this purpose an experiment was conducted in a greenhouse, comprising a sample size of 64 experimental swards such as pure swards of red clover (Trifolium pratense L.), white clover (Trifolium repens L.) and lucerne (Medicago sativa L.) as well as binary mixtures of each legume with perennial ryegrass (Lolium perenne L.). Growth stages ranged from tillering to heading and the proportion of legumes from 0 to 80 %. Based on digital sward images three steps were considered in order to estimate the legume contribution (% of DM): i) The development of a digital image analysis (DIA) procedure in order to estimate legume coverage (% of area). ii) The description of the relationship between legume coverage (% area) and legume contribution (% of DM) derived from digital analysis of legume coverage related to the green area in a digital image. iii) The estimation of the legume DM contribution with the findings of i) and ii). i) In order to evaluate the most suitable approach for the estimation of legume coverage by means of DIA different tools were tested. Morphological operators such as erode and dilate support the differentiation of objects of different shape by shrinking and dilating objects (Soille, 1999). When applied to digital images of legume-grass mixtures thin grass leaves were removed whereas rounder clover leaves were left. After this process legume leaves were identified by threshold segmentation. The segmentation of greyscale images turned out to be not applicable since the segmentation between legumes and bare soil failed. The advanced procedure comprising morphological operators and HSL colour information could determine bare soil areas in young and open swards very accurately. Also legume specific HSL thresholds allowed for precise estimations of legume coverage across a wide range from 11.8 - 72.4 %. Based on this legume specific DIA procedure estimated legume coverage showed good correlations with the measured values across the whole range of sward ages (R2 0.96, SE 4.7 %). A wide range of form parameters (i.e. size, breadth, rectangularity, and circularity of areas) was tested across all sward types, but none did improve prediction accuracy of legume coverage significantly. ii) Using measured reference data of legume coverage and contribution, in a first approach a common relationship based on all three legumes and sward ages of 35, 49 and 63 days was found with R2 0.90. This relationship was improved by a legume-specific approach of only 49- and 63-d old swards (R2 0.94, 0.96 and 0.97 for red clover, white clover, and lucerne, respectively) since differing structural attributes of the legume species influence the relationship between these two parameters. In a second approach biomass was included in the model in order to allow for different structures of swards of different ages. Hence, a model was developed, providing a close look on the relationship between legume coverage in binary legume-ryegrass communities and the legume contribution: At the same level of legume coverage, legume contribution decreased with increased total biomass. This phenomenon may be caused by more non-leguminous biomass covered by legume leaves at high levels of total biomass. Additionally, values of legume contribution and coverage were transformed to the logit-scale in order to avoid problems with heteroscedasticity and negative predictions. The resulting relationships between the measured legume contribution and the calculated legume contribution indicated a high model accuracy for all legume species (R2 0.93, 0.97, 0.98 with SE 4.81, 3.22, 3.07 % of DM for red clover, white clover, and lucerne swards, respectively). The validation of the model by using digital images collected over field grown swards with biomass ranges considering the scope of the model shows, that the model is able to predict legume contribution for most common legume-grass swards (Frame, 1992; Ledgard and Steele, 1992; Loges, 1998). iii) An advanced procedure for the determination of legume DM contribution by DIA is suggested, which comprises the inclusion of morphological operators and HSL colour information in the analysis of images and which applies an advanced function to predict legume DM contribution from legume coverage by considering total sward biomass. Low residuals between measured and calculated values of legume dry matter contribution were found for the separate legume species (R2 0.90, 0.94, 0.93 with SE 5.89, 4.31, 5.52 % of DM for red clover, white clover, and lucerne swards, respectively). The introduced DIA procedure provides a rapid and precise estimation of legume DM contribution for different legume species across a wide range of sward ages. Further research is needed in order to adapt the procedure to field scale, dealing with differing light effects and potentially higher swards. The integration of total biomass into the model for determining legume contribution does not necessarily reduce its applicability in practice as a combined estimation of total biomass and legume coverage by field spectroscopy (Biewer et al. 2009) and DIA, respectively, may allow for an accurate prediction of the legume contribution in legume-grass mixtures.

The role of ligneous vegetation for livestock nutrition in the sub-Sahelian and Sudanian zones of West Africa: Potential effects of climate change

Climate change and variability in sub-Saharan West Africa is expected to have negative consequences for crop and livestock farming due to the strong dependence of these sectors on rainfall and natural resources, and the low adaptive capacity of crops farmers, agro-pastoralist and pastoralists in the region. The objective of this PhD research was to investigate the anticipated impacts of expected future climate change and variability on nutrition and grazing management of livestock in the prevailing extensive agro-pastoral and pastoral systems of the Sahelian and Sudanian zones of Burkina Faso. To achieve this, three studies were undertaken in selected village territories (100 km² each) in the southern Sahelian (Taffogo), northern Sudanian (Nobere, Safane) and southern Sudanian (Sokouraba) zone of the country during 2009 and 2010. The choice of two villages in the northern Sudanian zone was guided by the dichotomy between intense agricultural land use and high population density near Safane, and lower agricultural land use in the tampon zone between the village of Nobere and the National Park Kaboré Tambi of Pô. Using global positioning and geographical information systems tools, the spatio-temporal variation in the use of grazing areas by cattle, sheep and goats, and in their foraging behaviour in the four villages was assessed by monitoring three herds each per species during a one-year cycle (Chapter 2). Maximum itinerary lengths (km/d) were observed in the hot dry season (March-May); they were longer for sheep (18.8) and cattle (17.4) than for goats (10.5, p<0.05). Daily total grazing time spent on pasture ranged from 6 - 11 h with cattle staying longer on pasture than small ruminants (p<0.05). Feeding time accounted for 52% - 72% of daily time on pasture, irrespective of species. Herds spent longer time on pasture and walked farther distances in the southern Sahelian than the two Sudanian zones (p<0.01), while daily feeding time was longer in the southern Sudanian than in the other two zones (p>0.05). Proportional time spent resting decreased from the rainy (June - October) to the cool (November - February) and hot dry season (p<0.05), while in parallel the proportion of walking time increased. Feeding time of all species was to a significantly high proportion spent on wooded land (tree crown cover 5-10%, or shrub cover >10%) in the southern Sahelian zone, and on forest land (tree crown cover >10%) in the two Sudanian zones, irrespective of season. It is concluded that with the expansion of cropland in the whole region, remaining islands of wooded land, including also fields fallowed for three or more years with their considerable shrub cover, are particularly valuable pasturing areas for ruminant stock. Measures must be taken that counteract the shrinking of wooded land and forests across the whole region, including also active protection and (re)establishment of drought-tolerant fodder trees. Observation of the selection behaviour of the above herds of cattle and small ruminant as far as browse species were concerned, and interviews with 75 of Fulani livestock keepers on use of browse as feed by their ruminant stock and as remedies for animal disease treatment was undertaken (Chapter 3) in order to evaluate the consequence of climate change for the contribution of browse to livestock nutrition and animal health in the extensive grazing-based livestock systems. The results indicated that grazing cattle and small ruminants do make considerable use of browse species on pasture across the studied agro-ecological zones. Goats spent more time (p<0.01) feeding on browse species than sheep and cattle, which spent a low to moderate proportion of their feeding time on browsing in any of the study sites. As far as the agro-ecological zones were concerned, the contribution of browse species to livestock nutrition was more important in the southern Sahelian and northern Sudanian zone than the southern Sudanian zone, and this contribution is higher during the cold and hot dry season than during the rainy season. A total of 75 browse species were selected on pasture year around, whereby cattle strongly preferred Afzelia africana, Pterocarpus erinaceus and Piliostigma sp., while sheep and goats primarily fed on Balanites aegyptiaca, Ziziphus mauritiana and Acacia sp. Crude protein concentration (in DM) of pods or fruits of the most important browse species selected by goats, sheep and cattle ranged from 7% to 13% for pods, and from 10% to 18% for foliage. The concentration of digestible organic matter of preferred browse species mostly ranged from 40% to 60%, and the concentrations of total phenols, condensed tannins and acid detergent lignin were low. Linear regression analyses showed that browse preference on pasture is strongly related to its contents (% of DM) of CP, ADF, NDF and OM digestibility. Interviewed livestock keepers reported that browse species are increasingly use by their grazing animals, while for animal health care use of tree- and shrub-based remedies decreased over the last two decades. It is concluded that due to climate change with expected negative impact on the productivity of the herbaceous layer of communal pastures browse fodder will gain in importance for animal nutrition. Therefore re-establishment and dissemination of locally adapted browse species preferred by ruminants is needed to increase the nutritional situation of ruminant stock in the region and contribute to species diversity and soil fertility restoration in degraded pasture areas. In Chapter 4 a combination of household surveys and participatory research approaches was used in the four villages, and additionally in the village of Zogoré (southern Sahelian zone) and of Karangasso Vigué (northern Sudanian zone) to investigate pastoralists’ (n= 76) and agro-pastoralists’ (n= 83) perception of climate change, and their adaptation strategies in crop and livestock production at farm level. Across the three agro-ecological zones, the majority of the interviewees perceived an increase in maximum day temperatures and decrease of total annual rainfall over the last two decades. Perceptions of change in climate patterns were in line with meteorological data for increased temperatures while for total rainfall farmers’ views contrasted the rainfall records which showed a slight increase of precipitation. According to all interviewees climate change and variability have negative impacts on their crop and animal husbandry, and most of them already adopted some coping and adaptation strategies at farm level to secure their livelihoods and reduce negative impacts on their farming system. Although these strategies are valuable and can help crop and livestock farmers to cope with the recurrent droughts and climate variability, they are not effective against expected extreme climate events. Governmental and non-governmental organisations should develop effective policies and strategies at local, regional and national level to support farmers in their endeavours to cope with climate change phenomena; measures should be site-specific and take into account farmers’ experiences and strategies already in place.

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.