On the Descriptional Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. We focus on the descriptional complexity of these automata, establishing two complexity measures that are both based on the description of t-sRL-automata in terms of so-called meta-instructions. We present some hierarchy results as well as a non-recursive trade-off between deterministic 2-sRL-automata and finite-state acceptors.

Mechanisms of residue mulch-induced cereal growth increases in West Africa

The use of crop residues (CR) has been widely reported as a means of increasing crop yields across West Africa. However, little has been done to compare the magnitude and mechanisms of CR effects systematically in the different agro-ecological zones of the region. To this end, a series of field trials with millet (Pennisetum glaucum L.), sorghum [Sorghum bicolor (L.) Moench], and maize (Zea mays L.) was conducted over a 4-yr period in the Sahelian, Sudanian, and Guinean zones of West Africa. Soils ranged in pH from 4.1 to 5.4 along a rainfall gradient from 510 to 1300 mm. Treatments in the factorial experiments were three CR rates (0,500, and 2000 kg ha^-1)and several levels of phosphorus and nitrogen. The results showed CR-induced total dry matter (TDM) increases in cereals up to 73% for the Sahel compared with a maximum of 16% in the wetter Sudanian and Guinean zones. Residue effects on weakly buffered Sahelian soils were due to improved P availability and to a protection of seedlings against wind erosion. Additional effects of CR mulching on topsoil properties in the Sahel were a decrease in peak temperatures by 4°C and increased water availability. These mulch effects on soil chemical and physical properties strongly decreased from North to South. Likely explanations for this decrease are the decline of dust deposition and wind erosion hazards, the higher soil clay content, lower air temperature, and a faster decomposition rate of mulch material with increasing rainfall from the Sahel to the Sudanian and Guinean zones.

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.