On the Gap-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. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one 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. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

Praxisrelevante Auswirkungen des Vorschlages für eine EU-Verordnung KOM/2000/7/final, 2000/0212(COD) des europäischen Parlaments und des Rates von der Kommission der Europäischen Gemeinschaften auf die Verkehrsplanung des öffentlichen Personennahverkehrs

Die Arbeit behandelt den Vorschlag für eine EU-Verordnung KOM/2000/7/final, 2000/0212(COD) des europäischen Parlaments und des Rates von der Kommission der Europäischen Gemeinschaften als Grundlage einer Marktöffnungsverordnung und welche Veränderungen sich dadurch in Deutschland einstellen werden. Ausschreibungen von Verkehrsleistungen werden zunehmen. Die Ausschreibungsarten werden sich in ländlichen Regionen von denen in Verkehrszentren unterscheiden. In der Region werden sich Bedarfslösungen stärker durchsetzen. Kürzungen von Verkehrsleistungen werden hier stärker ausfallen als in den Zentren und damit zu einem kleineren Leistungsvolumen führen. Aufgrund des geringen Leistungsumfangs gibt es weniger Interessenten. Bei Standardausschreibungen werden deshalb auch häufig die Varianten der beschränkten oder die freihändige Vergabe gewählt. Funktionale Ausschreibungen haben nur eine untergeordnete Bedeutung. In den Verkehrszentren sind die Lose größer und damit für viele Anbieter interessant. Die Verkehrszusatzleistungen sind zudem komplexer. Standardausschreibungen in öffentlicher Vergabeart werden sich hier vermutlich als Norm durchsetzen. Die VOL/A wird sicherlich ihre Bedeutung und ihren dafür notwendigen Regelungsumfang in Deutschland als deutsches oder als europäisches Recht behalten. Ob der empfehlende Charakter der DIN EN 13816 Norm „ÖPNV: Definition, Festlegung von Leistungszielen und Messung der Servicequalität“ erhalten werden kann und nicht als Steuerungselement zur Standardisierung im ÖPNV beitragen wird, ist dabei zu bezweifeln. Durch diese Wettbewerbspflicht wird der Aufgabenträger zum Besteller von Verkehrsleistungen. Damit geht die Verkehrsplanung in die Verantwortung des Aufgabenträgers über und gerät stärker in den Einflussbereich der Politik. Die strategisch abstrakte und die konkrete Verkehrsplanung wachsen für den Normfall der Standardausschreibung zusammen. Die Hoffnung auf eine bessere Netzintegration und eine Standardisierung des ÖPNV Angebots und der ÖPNV Qualität entsteht. Es entwickelt sich dadurch aber auch die Gefahr der Abhängigkeit des Nahverkehrsangebots von der derzeitigen Haushaltslage oder der Interessenlage der Politik. Kontinuität in Angebot und Qualität werden zu erklärten Planungszielen. Der Verkehrsplaner auf der Bestellerseite muss die Planung in Ausschreibungsunterlagen umsetzen. Dies erfordert erweiterte Kompetenzen in den Bereichen Betriebswirtschaft, Logistik, Jura, Informatik und Führungskompetenzen. Ausbildende Institutionen müssen darauf bereits im Vorfeld der Umsetzung reagieren. Durch die zeitliche Verzögerung der Umsetzung der Planung durch die Ausschreibungsschritte sind in der Verkehrsplanung längere Planungsvorlaufzeiten einzukalkulieren. Vorausschauender zu planen, wird dabei wichtiger. Auch eventuelle Fehler in der Planung sind nicht mehr so einfach zu korrigieren. Durch den gestiegenen Einsatz von Technologien in den Fahrzeugen besteht für den Verkehrsplaner dafür häufiger die Möglichkeit, Planungsänderungen auf ihre Wirksamkeit im Hinblick auf Attraktivität für den Fahrgast anhand von den ermittelten Fahrgastzahlen zu kontrollieren. Dasselbe gilt auch für Marketing- und Vertriebsmaßnahmen, wie für die Tarifpolitik. Die Zahlen stehen nicht nur für diese Rückkopplung zur Verfügung, sondern dienen auch als Planungsgrundlage für zukünftige Maßnahmen. Dem Planer stehen konkretere Zahlen für die Planung zur Verfügung. Ein Aspekt, der aufgrund der Sanktionsmaßnahmen bei Ausschreibungen an Bedeutung gewinnen wird, ist die Möglichkeit, Qualität von Verkehrsleistungen möglichst objektiv beurteilen zu können. Praxisrelevante Auswirkungen auf die Verkehrsplanung des öffentlichen Personennahverkehrs ergeben sich hauptsächlich durch die gestiegene Komplexität in der Planung selbst und den dadurch unverzichtbaren gewordenen Einsatz von Computerunterstützung. Die Umsetzung in Ausschreibungsunterlagen der Planung und die Kontrolle stellen neue Elemente im Aufgabenbereich des Verkehrsplaners dar und erfordern damit breiter ausgelegte Kernkompetenzen. Es werden mehr Verkehrsplaner mit breiterer Ausbildung benötigt werden. Diese Arbeit hat aufgezeigt, dass sich mit der Integration des Ausschreibungsgedankens in den Ablauf der Verkehrsplanung eine sprunghafte Entwicklung in der Planungstätigkeit ergeben wird. Aufgrund der in Zukunft steigenden Qualität und Quantität der Planungsgrundlagen und der ebenfalls gestiegenen Ansprüche an die Bewertungsparameter ergeben sich Veränderungen und neue Anforderungen auf diesem Gebiet, die in erster Linie für die Hochschulen und andere ausbildende Einrichtungen, aber auch für die Verkehrsplanung unterstützende Industrie.

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.

Reduced L_1 level width and Coster-Kronig yields by relaxation and continuum interactions in atomic zinc

Calculations of the level width \gamma( L_1) and the f_12 and f_13 Coster-Kronig yields for atomic zinc have been performed with Dirac-Fock wave functions. For \gamma(L_1), a large deviation between theory and evaluated data exists. We include the incomplete orthogonality of the electron orbitals as well as the interchannel interaction of the decaying states. Orbital relaxation reduces the total rates in all groups of the electron-emission spectrum by about 10-20 %. Different, however, is the effect of the continuum interaction. The L_1-L_23X Coster-Kronig part of the spectrum is definitely reduced in its intensity, whereas the MM and MN spectra are slightly enhanced. This results in a reduction of Coster-Kronig yields, where for medium and heavy elements considerable discrepancies have been found in comparison to relativistic theory. Briefly, we discuss the consequences of our calculations for heavier elements.

River ecosystems at risk

Worldwide water managers are increasingly challenged to allocate sufficient and affordable water supplies to different water use sectors without further degrading river ecosystems and their valuable services to mankind. Since 1950 human population almost tripled, water abstractions increased by a factor of four, and the number of large dam constructions is about eight times higher today. From a hydrological perspective, the alteration of river flows (temporally and spatially) is one of the main consequences of global change and further impairments can be expected given growing population pressure and projected climate change. Implications have been addressed in numerous hydrological studies, but with a clear focus on human water demands. Ecological water requirements have often been neglected or addressed in a very simplistic manner, particularly from the large-scale perspective. With his PhD thesis, Christof Schneider took up the challenge to assess direct (dam operation and water abstraction) and indirect (climate change) impacts of human activities on river flow regimes and evaluate the consequences for river ecosystems by using a modeling approach. The global hydrology model WaterGAP3 (developed at CESR) was applied and further developed within this thesis to carry out several model experiments and assess anthropogenic river flow regime modifications and their effects on river ecosystems. To address the complexity of ecological water requirements the assessment is based on three main ideas: (i) the natural flow paradigm, (ii) the perception that different flows have different ecological functions, and (iii) the flood pulse concept. The thesis shows that WaterGAP3 performs well in representing ecologically relevant flow characteristics on a daily time step, and therefore justifies its application within this research field. For the first time a methodology was established to estimate bankfull flow on a 5 by 5 arc minute grid cell raster globally, which is a key parameter in eFlow assessments as it marks the point where rivers hydraulically connect to adjacent floodplains. Management of dams and water consumption pose a risk to floodplains and riparian wetlands as flood volumes are significantly reduced. The thesis highlights that almost one-third of 93 selected Ramsar sites are seriously affected by modified inundation patterns today, and in the future, inundation patterns are very likely to be further impaired as a result of new major dam initiatives and climate change. Global warming has been identified as a major threat to river flow regimes as rising temperatures, declining snow cover, changing precipitation patterns and increasing climate variability are expected to seriously modify river flow regimes in the future. Flow regimes in all climate zones will be affected, in particular the polar zone (Northern Scandinavia) with higher river flows during the year and higher flood peaks in spring. On the other side, river flows in the Mediterranean are likely to be even more intermittent in the future because of strong reductions in mean summer precipitation as well as a decrease in winter precipitation, leading to an increasing number of zero flow events creating isolated pools along the river and transitions from lotic to lentic waters. As a result, strong impacts on river ecosystem integrity can be expected. Already today, large amounts of water are withdrawn in this region for agricultural irrigation and climate change is likely to exacerbate the current situation of water shortages.