On the generalized obnoxious center problem: antimedian subsets

The set of vertices that maximize (minimize) the remoteness is the antimedian (median) set of the profile. It is proved that for an arbitrary graph G and S V (G) it can be decided in polynomial time whether S is the antimedian set of some profile. Graphs in which every antimedian set is connected are also considered.

Enhancement of Calcifications in Mammograms using Volterra Series based Quadratic Filter

The paper summarizes the design and implementation of a quadratic edge detection filter, based on Volterra series, for enhancing calcifications in mammograms. The proposed filter can account for much of the polynomial nonlinearities inherent in the input mammogram image and can replace the conventional edge detectors like Laplacian, gaussian etc. The filter gives rise to improved visualization and early detection of microcalcifications, which if left undetected, can lead to breast cancer. The performance of the filter is analyzed and found superior to conventional spatial edge detectors

Quadratic Predictor based Differential Encoding and Decoding of Speech Signals

Modeling nonlinear systems using Volterra series is a century old method but practical realizations were hampered by inadequate hardware to handle the increased computational complexity stemming from its use. But interest is renewed recently, in designing and implementing filters which can model much of the polynomial nonlinearities inherent in practical systems. The key advantage in resorting to Volterra power series for this purpose is that nonlinear filters so designed can be made to work in parallel with the existing LTI systems, yielding improved performance. This paper describes the inclusion of a quadratic predictor (with nonlinearity order 2) with a linear predictor in an analog source coding system. Analog coding schemes generally ignore the source generation mechanisms but focuses on high fidelity reconstruction at the receiver. The widely used method of differential pnlse code modulation (DPCM) for speech transmission uses a linear predictor to estimate the next possible value of the input speech signal. But this linear system do not account for the inherent nonlinearities in speech signals arising out of multiple reflections in the vocal tract. So a quadratic predictor is designed and implemented in parallel with the linear predictor to yield improved mean square error performance. The augmented speech coder is tested on speech signals transmitted over an additive white gaussian noise (AWGN) channel.

Design, Development and Realization of Quadratic Volterra Filters for Selected Applications

The basic concepts of digital signal processing are taught to the students in engineering and science. The focus of the course is on linear, time invariant systems. The question as to what happens when the system is governed by a quadratic or cubic equation remains unanswered in the vast majority of literature on signal processing. Light has been shed on this problem when John V Mathews and Giovanni L Sicuranza published the book Polynomial Signal Processing. This book opened up an unseen vista of polynomial systems for signal and image processing. The book presented the theory and implementations of both adaptive and non-adaptive FIR and IIR quadratic systems which offer improved performance than conventional linear systems. The theory of quadratic systems presents a pristine and virgin area of research that offers computationally intensive work. Once the area of research is selected, the next issue is the choice of the software tool to carry out the work. Conventional languages like C and C++ are easily eliminated as they are not interpreted and lack good quality plotting libraries. MATLAB is proved to be very slow and so do SCILAB and Octave. The search for a language for scientific computing that was as fast as C, but with a good quality plotting library, ended up in Python, a distant relative of LISP. It proved to be ideal for scientific computing. An account of the use of Python, its scientific computing package scipy and the plotting library pylab is given in the appendix Initially, work is focused on designing predictors that exploit the polynomial nonlinearities inherent in speech generation mechanisms. Soon, the work got diverted into medical image processing which offered more potential to exploit by the use of quadratic methods. The major focus in this area is on quadratic edge detection methods for retinal images and fingerprints as well as de-noising raw MRI signals

Bieberbach's Conjecture, the de Branges and Weinstein Functions and the Askey-Gasper Inequality

The Bieberbach conjecture about the coefficients of univalent functions of the unit disk was formulated by Ludwig Bieberbach in 1916 [Bieberbach1916]. The conjecture states that the coefficients of univalent functions are majorized by those of the Koebe function which maps the unit disk onto a radially slit plane. The Bieberbach conjecture was quite a difficult problem, and it was surprisingly proved by Louis de Branges in 1984 [deBranges1985] when some experts were rather trying to disprove it. It turned out that an inequality of Askey and Gasper [AskeyGasper1976] about certain hypergeometric functions played a crucial role in de Branges' proof. In this article I describe the historical development of the conjecture and the main ideas that led to the proof. The proof of Lenard Weinstein (1991) [Weinstein1991] follows, and it is shown how the two proofs are interrelated. Both proofs depend on polynomial systems that are directly related with the Koebe function. At this point algorithms of computer algebra come into the play, and computer demonstrations are given that show how important parts of the proofs can be automated.

Learning analysis by reduction from positive data

Analysis by reduction is a linguistically motivated method for checking correctness of a sentence. It can be modelled by restarting automata. In this paper we propose a method for learning restarting automata which are strictly locally testable (SLT-R-automata). The method is based on the concept of identification in the limit from positive examples only. Also we characterize the class of languages accepted by SLT-R-automata with respect to the Chomsky hierarchy.

Orthogonal polynomials and recurrence equations, operator equations and factorization

This article surveys the classical orthogonal polynomial systems of the Hahn class, which are solutions of second-order differential, difference or q-difference equations. Orthogonal families satisfy three-term recurrence equations. Example applications of an algorithm to determine whether a three-term recurrence equation has solutions in the Hahn class - implemented in the computer algebra system Maple - are given. Modifications of these families, in particular associated orthogonal systems, satisfy fourth-order operator equations. A factorization of these equations leads to a solution basis.

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.

A generic formula for the values at the boundary points of monic classical orthogonal polynomials

In a previous paper we have determined a generic formula for the polynomial solution families of the well-known differential equation of hypergeometric type σ(x)y"n(x)+τ(x)y'n(x)-λnyn(x)=0. In this paper, we give another such formula which enables us to present a generic formula for the values of monic classical orthogonal polynomials at their boundary points of definition.

Solution properties of the de Branges differential recurrence equation

In this 1984 proof of the Bieberbach and Milin conjectures de Branges used a positivity result of special functions which follows from an identity about Jacobi polynomial sums thas was published by Askey and Gasper in 1976. The de Branges functions Tn/k(t) are defined as the solutions of a system of differential recurrence equations with suitably given initial values. The essential fact used in the proof of the Bieberbach and Milin conjectures is the statement Tn/k(t)<=0. In 1991 Weinstein presented another proof of the Bieberbach and Milin conjectures, also using a special function system Λn/k(t) which (by Todorov and Wilf) was realized to be directly connected with de Branges', Tn/k(t)=-kΛn/k(t), and the positivity results in both proofs Tn/k(t)<=0 are essentially the same. In this paper we study differential recurrence equations equivalent to de Branges' original ones and show that many solutions of these differential recurrence equations don't change sign so that the above inequality is not as surprising as expected. Furthermore, we present a multiparameterized hypergeometric family of solutions of the de Branges differential recurrence equations showing that solutions are not rare at all.

Church-Rosser groups and growing context-sensitive groups

A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.

Functions satisfying holonomic q-differential equations

In a similar manner as in some previous papers, where explicit algorithms for finding the differential equations satisfied by holonomic functions were given, in this paper we deal with the space of the q-holonomic functions which are the solutions of linear q-differential equations with polynomial coefficients. The sum, product and the composition with power functions of q-holonomic functions are also q-holonomic and the resulting q-differential equations can be computed algorithmically.

Parity of the Number of Irreducible Factors for Composite Polynomials

Various results on parity of the number of irreducible factors of given polynomials over finite fields have been obtained in the recent literature. Those are mainly based on Swan’s theorem in which discriminants of polynomials over a finite field or the integral ring Z play an important role. In this paper we consider discriminants of the composition of some polynomials over finite fields. The relation between the discriminants of composed polynomial and the original ones will be established. We apply this to obtain some results concerning the parity of the number of irreducible factors for several special polynomials over finite fields.

Einfluß der Gewässerversauerung auf Hyporheos und Bryorheos: Untersuchungen an zwei Waldbächen im Westharz

Im Rahmen der Fallstudie Harz sollte an der Schnittstelle zwischen Grundlagenforschung und angewandter Forschung ein Beitrag zur Klärung der Frage geleistet werden, inwieweit zwei Zuläufe der Sösetalsperre im Westharz versauert bzw. versauerungsgefährdet sind; aus diesem Stausee wird Trinkwasser für mehrere Gemeinden in Norddeutschland gewonnen. Die Belastung des fast vollständig bewaldeten Einzugsgebiets der Sösetalsperre mit luftbürtigen Schadstoffen (Saurer Regen) zählte zu den höchsten in Mitteleuropa. An jeweils drei Untersuchungsstellen der beiden Bäche Alte Riefensbeek (R1 bis R3) und Große Söse (S1 bis S3) wurden zwischen März 1987 und November 1988 Proben aus Moospolstern und dem hyporheischen Interstitial entnommen und physikalisch, chemisch und biologisch untersucht. Ergänzend wurden Wasserproben zwischen März 1986 und Oktober 1991 sowie vom April 1998 ebenso wie qualitative Fänge von Makroinvertebraten zwischen November 1986 und Juli 1990 sowie vom April 1998 ausgewertet. Die Analyse der tierischen Besiedlung der Moos- und Interstitialproben beschränkte sich auf die taxonomischen Gruppen Turbellaria (Strudelwürmer), Mollusca (Weichtiere), Amphipoda (Flohkrebse), Ephemeroptera (Eintagsfliegen), Plecoptera (Steinfliegen), Heteroptera (Wanzen), Megaloptera (Schlammfliegen), Coleoptera (Käfer), Trichoptera (Köcherfliegen) und Diptera (Zweiflügler). Der Grundsatz, daß normalverteilte und nicht normalverteilte Daten statistisch unterschiedlich behandelt werden müssen, wurde konsequent angewandt. Am Beispiel der Choriotopstruktur wurde gezeigt, daß die Auswahl des Analyseverfahrens das Ergebnis der ökologischen Interpretation multivariater statistischer Auswertung beeinflußt. Die Daten der Korngrößen-Verteilung wurden vergleichend einer univariaten und einer multivariaten statistischen Analyse unterworfen. Mit dem univariaten Verfahren wurden die Gradienten der ökologisch relevanten Korngrößen-Parameter eher erkannt als mit dem multivariaten Verfahren. Die Auswirkungen von Gewässerversauerung sowie anderer Umweltfaktoren (insgesamt 42 Faktoren) auf die Lebensgemeinschaften wurden anhand der Parameter Artenzahl, Besiedlungsdichte, Körpergröße und Biomasse untersucht. Abundanz, Biomasse und Körpergröße sowie die Umweltfaktoren wurden auf einem horizontalen Gradienten, d.h. im Längslauf der Bäche, und auf einem vertikalen Gradienten, d.h. fließende Welle / Bryorheon / Benthon versus Hyporheon, untersucht. Es wurde ein terminologisches System für die Kompartimente in der Fließgewässer-Aue vorgeschlagen, das in sich einheitlich ist. Es wurde ein neuer Moos-Vitalitätsindex für die Moospolster vorgestellt. Es wurden Bestimmungsschlüssel für die Larven der Chloroperlidae (Steinfliegen-Familie) und der Empididae (Tanzfliegen) in den beiden Harzbächen entwickelt. Die untersuchten Bachstrecken waren frei von Abwasserbelastung. An zwei Stellen wurde Wasser für einen Forellenteich ausgeleitet. Abgesehen von zwei meterhohen Abstürzen in der Großen Söse waren wasserbauliche Veränderungen ohne große Bedeutung. Das Abfluß-Regime war insofern nicht mehr natürlich, als beide Bäche in das System der bergbaulichen Bewässerungsgräben des Oberharzes eingebunden sind. Die Söse hatte ein F-nivopluviales Abfluß-Regime, der abflußreichste Doppelmonat war der März / April, die Unregelmäßigkeit des Abfluß-Regimes war sehr hoch, die Vorhersagbarkeit sehr niedrig, die monatlichen Abfluß-Maxima wiesen eine sehr geringe Konstanz auf. Der Zeitraum der biologischen Probenahme wurde von überdurchschnittlich vielen Tagen mit mäßig erhöhten Abflüssen geprägt, sehr große Hochwasser-Wellen fehlten aber. Die Abfluß-Dynamik wurde statistisch beschrieben. Das hydraulische Regime wurde anhand der Meßgrößen Fließgeschwindigkeit, Fließkraft und FROUDE-Zahl dargestellt. Der Zusammenhang zwischen Abfluß und Fließgeschwindigkeit auf der einen Seite und der Korngrößen-Verteilung auf der anderen Seite wurde statistisch untersucht, ebenfalls zwischen dem Abfluß und dem Kohlenstoff- und Stickstoff-Gehalt der Feinstpartikel sowie dem Wasserchemismus. In den Phasen ohne Hochwasser hatte das Hyporheal die Funktion einer Senke für Feinstkörner. Das Bachbett der Alten Riefensbeek war stabiler als das der Großen Söse. Insgesamt gesehen war das hyporheische Sediment in den quellnahen Abschnitten grobkörniger und auf den quellfernen Strecken feinkörniger. Der prozentuale Anteil der Feinstkörner im Hyporheal und Benthal nahm aber im Längslauf der Bäche ab. Dies ist ungewöhnlich, konnte aber nicht plausibel mit geologischen und hydrologischen Meßgrößen erklärt werden. Beide Bäche waren sommerkalt. Der Einfluß der Wassertemperatur auf die Larvalentwicklung wurde beispielhaft an den Taxa Baetis spp. und Leuctra gr. inermis untersucht. Es gab eine Tendenz, daß der Kohlenstoff- und Stickstoff-Gehalt der Feinstpartikel vom Benthal in das Hyporheal anstieg. Dies war ein weiterer Hinweis darauf, daß das Hyporheal die Funktion einer Senke und Vorratskammer für Nährstoffe hat. Der Zusammenhang zwischen partikulärer und gelöster Kohlenstoff-Fraktion wurde diskutiert. Im Hyporheon war die Nitrifikation nicht stärker als in der fließenden Welle. Es gab Hinweise, daß die sauren pH-Werte in der Großen Söse die Nitrifikation hemmten. Die Valenzen der Moos- und Tier-Taxa bezüglich Fließgeschwindigkeit, pH-Wert, Alkalinität sowie der Gehalte von Sauerstoff, Calcium, Magnesium, Kalium und Natrium wurden zusammengestellt. Das hyporheische Sediment war sehr grob und hatte eine hohe Porosität. Der Austausch zwischen fließender Welle und hyporheischem Wasser konnte deshalb sehr schnell erfolgen, es gab keine intergranulare Sprungschicht, die physikalischen und chemischen Tiefengradienten waren in den meisten Fällen gar nicht ausgeprägt oder nur sehr flach. Die Wassertemperatur des Freiwassers unterschied sich nicht signifikant von derjenigen im hyporheischen Wasser. Es gab -- von wenigen Ausnahmen bei pH-Wert, Leitfähigkeit und Sauerstoffgehalt abgesehen -- keine signifikanten Unterschiede zwischen dem Wasserchemismus der fließenden Welle und dem des Hyporheals. Die physikalischen und chemischen Voraussetzungen für die Refugialfunktion des Hyporheons waren deshalb für versauerungsempfindliche Taxa nicht gegeben. In der Tiefenverteilung der untersuchten Tiergruppen im Hyporheal lag das Maximum der Abundanz bzw. Biomasse häufiger in 10 cm als in 30 cm Tiefe. Daraus läßt sich aber keine allgemeine Gesetzmäßigkeit ableiten. Es wurde durchgehend die Definition angewendet, daß die Gewässerversauerung durch den Verlust an Pufferkapazität charakterisiert ist. Saure Gewässer können, müssen aber nicht versauert sein; versauerte Gewässer können, müssen aber nicht saures Wasser haben. Maßstab für das Pufferungsvermögen eines Gewässers ist nicht der pH-Wert, sondern sind die Alkalinität und andere chemische Versauerungsparameter. Der pH-Wert war auch operativ nicht als Indikator für Gewässerversauerung anwendbar. Die chemische Qualität des Bachwassers der Großen Söse entsprach aufgrund der Versauerung nicht den umweltrechtlichen Vorgaben bezüglich der Parameter pH-Wert, Aluminium, Eisen und Mangan, bzgl. Zink galt dies nur an S1. In der Alten Riefensbeek genügte das Hyporheal-Wasser in 30 cm Tiefe an R2 bzgl. des Sauerstoff-Gehalts nicht den umweltrechtlichen Anforderungen. Nur im Freiwasser an R1 genügten die Ammonium-Werte den Vorgaben der EG-Fischgewässer-Richtlinie, der Grenzwert wurde an allen anderen Meßstellen und Entnahmetiefen überschritten. Das BSB-Regime in allen Entnahmetiefen an R2, im Freiwasser an R3 und S1, im Hyporheal an R1 sowie in 30 cm Tiefe an R3 genügte nicht den Anforderungen der Fischgewässer-Richtlinie. Der Grenzwert für Gesamt-Phosphor wurde an S3 überschritten. In der Großen Söse war der Aluminium-Gehalt so hoch, daß anorganisches und organisches Aluminium unterschieden werden konnten. Besonders hohe Gehalte an toxischem anorganischen Aluminium wurden an Tagen mit Spitzen-Abflüssen und Versauerungsschüben gemessen. Erst die Ermittlung verschiedener chemischer Versauerungsparameter zeigte, daß auch die alkalischen Probestellen R2 und R3 mindestens versauerungsempfindlich waren. Die Messung bzw. Berechnung von chemischen Versauerungsparametern sollte deshalb zum Routineprogramm bei der Untersuchung von Gewässerversauerung gehören. Zu Beginn des Untersuchungsprogramms war angenommen worden, daß die mittleren und unteren Abschnitte der Alten Riefensbeek unversauert sind. Dieser Ansatz des Untersuchungsprogramms, einen unversauerten Referenzbach (Alte Riefensbeek) mit einem versauerten Bach (Große Söse) zu vergleichen, mußte nach der Berechnung von chemischen Versauerungsindikatoren sowie der Analyse der Abundanz- und Biomasse-Werte modifiziert werden. Es gab einen Versauerungsgradienten entlang der Probestellen: R1 (unversauert) R2 und R3 (versauerungsempfindlich bis episodisch leicht versauert) S2 und S3 (dauerhaft versauert) S1 (dauerhaft stark versauert). An S1 war das Hydrogencarbonat-Puffersystem vollständig, an S2 und S3 zeitweise ausgefallen. Die Versauerungslage an R2 und R3 war also schlechter als vorausgesehen. Unterschiede im Versauerungsgrad zwischen den Meßstellen waren nicht so sehr in unterschiedlichen Eintragsraten von versauernden Stoffen aus der Luft begründet, sondern in unterschiedlichen Grundgesteinen mit unterschiedlichem Puffervermögen. Der Anteil der verschiedenen sauren Anionen an der Versauerung wurde untersucht, die chemischen Versauerungsmechanismen wurden mit Hilfe von Ionenbilanzen und verschiedenen Versauerungsquotienten analysiert. Die beiden untersuchten Bäche waren von anthropogener Versauerung betroffen. Dabei spielte die Schwefel-Deposition (Sulfat) eine größere Rolle als die Stickstoff-Deposition (Nitrat). Die Probestelle S1 war immer schon in unbekanntem Maß natürlich sauer. Dieser natürlich saure Zustand wurde von der hinzugekommenen anthropogenen Versauerung bei weitem überragt. Die wenigen gewässerökologischen Daten, die im Wassereinzugsgebiet der Söse vor 1986 gewonnen wurden, deuten darauf hin, daß die Versauerung in den 70er und in der ersten Hälfte der 80er Jahre vom Boden und Gestein in die Bäche durchgeschlagen war. Dieser Versauerungsprozeß begann vermutlich vor 1973 in den Quellen auf dem Acker-Bruchberg und bewegte sich im Laufe der Jahre immer weiter talwärts in Richtung Trinkwasser-Talsperre. Der Mangel an (historischen) freilandökologischen Grundlagendaten war nicht nur im Untersuchungsgebiet, sondern ist allgemein in der Versauerungsforschung ein Problem. Wenn sich das Vorkommen von nah verwandten Arten (weitgehend) ausschließt, kann dies an der Versauerung liegen, z.B. war die Alte Riefensbeek ein Gammarus-Bach, die Große Söse ein Niphargus-Bach; dieses muß aber nicht an der Versauerung liegen, z.B. fehlte Habroleptoides confusa im Hyporheos an R3, Habrophlebia lauta hatte dagegen ihr Abundanz- und Biomasse-Maximum an R3. Zugleich lag das Maximum des prozentualen Anteils von Grobsand an R3, eine mögliche Ursache für diese interspezifische Konkurrenz. Die biologische Indikation von Gewässerversauerung mit Hilfe der Säurezustandsklassen funktionierte nicht in den beiden Harzbächen. Es wurde deshalb ein biologischer Versauerungsindex vorgeschlagen; dieser wurde nicht am pH-Wert kalibriert, sondern an der chemischen Versauerungslage, gekennzeichnet durch die Alkalinität und andere chemische Meßgrößen der Versauerung. Dafür wurden aufgrund der qualitativen und quantitativen Daten die häufigeren Taxa in die vier Klassen deutlich versauerungsempfindlich, mäßig versauerungsempfindlich, mäßig versauerungstolerant und deutlich versauerungstolerant eingeteilt. Es reicht nicht aus, die biologischen Folgen von Gewässerversauerung sowie Veränderungen in der Nährstoff-Verfügbarkeit und im sonstigen Wasserchemismus nur anhand der Artenzahl oder des Artenspektrums abzuschätzen. Vielmehr müssen quantitative Methoden wie die Ermittlung der Abundanzen angewandt werden, um anthropogene und natürliche Störungen des Ökosystems zu erfassen. Es wurde eine Strategie für die behördliche Gewässergüteüberwachung von Bachoberläufen vorgeschlagen, die flächendeckend die Versauerungsgefährdung erfassen kann. Die Auswirkungen der zeitlichen Dynamik des Versauerungschemismus wurden am Beispiel des versauerungsempfindlichen Taxons Baetis spp. (Eintagsfliegen) dargestellt. An S2 und S3 kam es zu starken Versauerungsschüben. Baetis konnte sich nicht ganzjährig halten, sondern nur in versauerungsarmen Phasen im Sommer und im Herbst; es gab einen Besiedlungskreislauf aus Ausrottungs- und Wiederbesiedlungsphasen. Die temporäre Population von Baetis an S2 und S3 bestand nur aus ersten Larvenstadien. Die Probestellen wurden auf horizontalen Gradienten der Umweltfaktoren angeordnet. Bei einigen Parametern gab es keinen Gradienten (z.B. Sauerstoff-Gehalt), bei anderen Parametern waren die Meßstellen auf sehr flachen Gradienten angeordnet (z.B. C:N-Quotient der Feinstkörner), bei den restlichen Meßgrößen waren die Gradienten sehr deutlich (z.B. Alkalinität). Bei den Längsgradienten von Abundanz und Biomasse waren alle Möglichkeiten vertreten: Zunahme (z.B. Leuctra pseudosignifera), Abnahme (z.B. Gammarus pulex), Maximum an der mittleren Probestelle (z.B. Leuctra pseudocingulata) und kein signifikanter Trend (z.B. Nemoura spp.). Abundanz und Biomasse zahlreicher taxonomischer Einheiten hatten ihr Maximum im Längslauf an den quellnächsten Probestellen R1 und S1, z.B. Protonemura spp. und Plectrocnemia spp. Die Lebensgemeinschaften an R1 und S1 waren allerdings völlig unterschiedlich zusammengesetzt. Die häufig vertretene Annahme, versauerte Gewässer seien biologisch tot, ist falsch. Unter Anwendung des 3. biozönotischen Grundprinzips wurde das Maximum von Abundanz und Biomasse in den quellnahen Abschnitten mit dem eustatistischen (stabilen) Regime von Wassertemperatur, Abfluß und Protonen-Gehalt, in der Alten Riefensbeek auch von Alkalinität und ALMER-Relation erklärt. Aufgrund der natürlichen und anthropogenen Störungen war im Längslauf der untersuchten Bäche keine natürliche biozönotische Gliederung des Artenbestands erkennbar. Die Korrelationsberechnungen zwischen den Umweltfaktoren und der Taxazahl ergaben, daß in erster Linie versauerungsrelevante Parameter -- Gehalte saurer Anionen, basischer Kationen und von Metallen, Alkalinität usw. -- die höchsten Korrelationskoeffizienten mit der Taxa-Zahl hatten; unter den natürlichen Meßgrößen zählten nur die Gehalte von DOC und TIC sowie der Anteil der Sande zu der Gruppe mit den höchsten Korrelationskoeffizienten. Die Korrelationsberechnungen zwischen den Umweltfaktoren und den Abundanzen ergab dagegen, daß die quantitative Zusammensetzung der Lebensgemeinschaft nicht nur durch die anthropogene Gewässerversauerung, sondern mindestens genauso durch einige natürliche Meßgrößen beeinflußt wurde. Es gab in den Harzbächen keinen ökologischen Superfaktor, der die quantitative Zusammensetzung der Lebensgemeinschaft überwiegend bestimmte. Auch die Meßgrößen der anthropogenen Gewässerversauerung waren nicht solch ein Superfaktor. Einen ähnlich hohen Einfluß auf die quantitative Zusammensetzung der Lebensgemeinschaft hatten die geologisch bestimmten Umweltfaktoren Leitfähigkeit und TIC-Gehalt, der von der Landnutzung bestimmte DOC-Gehalt sowie der Chlorid-Gehalt, der geologisch, möglicherweise aber auch durch den Eintrag von Straßensalz bestimmt wird. Die Mischung von anthropogenen und natürlichen Faktoren wurde in einem Modell der Wirkung von abiotischen Faktoren auf Bryorheos und Hyporheos dargestellt. Als Beispiel für die zeitliche Nutzung ökologischer Nischen wurde die Verteilung der Larven und Adulten der Dryopidae (Hakenkäfer) im Hyporheos und Bryorheos untersucht. Die Larven wurden vorzugsweise im Hyporheon, die Adulten im Bryorheon angetroffen. Die untersuchten Taxa wurden in die Varianten bryorheobiont, bryorheophil, bryorheotolerant, bryorheoxen und bryorheophob bzw. hyporheobiont, hyporheophil, hyporheotolerant, hyporheoxen und hyporheophob eingeteilt, um ihre räumliche Nutzung ökologischer Nischen zu beschreiben. Die gängige Lehrmeinung, daß das Hyporheon die Kinderstube benthaler Makroinvertebraten ist, konnte für zahlreiche Taxa bestätigt werden (z.B. Habrophlebia lauta). Für die bryorheophilen Taxa (z.B. Gammarus pulex und Baetis spp.) trifft diese Lehrmeinung in den beiden Harzbächen nicht zu. Vielmehr übernimmt das Bryorheon die Funktion einer Kinderstube. Die Larven von Plectrocnemia conspersa / geniculata sowie von Baetis spp. und Amphinemura spp. / Protonemura spp. neben Gammarus pulex zeigten eine Habitatbindung, die erstgenannte Gattung an das Hyporheal, die letztgenannten 3 Taxa an untergetauchte Moospolster (Bryorheal). Die Idee von der Funktion des Hyporheals als Kinderstube der Larven und Jungtiere, als Schutzraum gegen die Verdriftung durch Strömung und vor Fraßdruck durch Räuber sowie als Ort hohen Nahrungsangebots mußte für die letztgenannten 3 Taxa abgelehnt werden. Für sie übernahm das Bryorheal diese Aufgaben. Zwar waren die beiden Bäche oligotroph und die Nahrungsqualität der Feinstkörner im Hyporheal war niedrig. Die Abundanz- und Biomasse-Werte im Bryorheos und Hyporheos gehörten aber zu den weltweit höchsten. Es wurde das Paradoxon diskutiert, daß im Hyporheon der beiden Bäche Diatomeen-Rasen gefunden wurden, obwohl das Hyporheon lichtlos sein soll. Das Hyporheon wurde als ein Ökoton zwischen Benthon / Rheon und Stygon angesehen. Es wurden vier Haupttypen des Hyporheons beschrieben. Wegen des sehr unterschiedlichen Charakters des Hyporheons in verschiedenen Fließgewässern gibt es keinen einheitlichen Satz von abiotischen und biotischen Faktoren, mit denen das Hyporheon vom Benthon und Stygon abgegrenzt werden kann. In den beiden Harzbächen ähnelte das Hyporheon mehr dem Benthon als dem Stygon. Es konnte nicht anhand der chemischen Meßgrößen vom Benthon abgegrenzt werden, sondern anhand der physikalischen Meßgrößen Trübung und der Anteile von Feinsand und Schluffe/Tone sowie anhand der biologischen Parameter Summen-Abundanz und Summen-Biomasse. Aus der Typologie des Hyporheons folgt, daß ein bestimmtes Hyporheon nicht alle in der Literatur beschriebenen Funktionen innerhalb der Fließgewässer-Aue übernehmen kann. Es wurde ein Schema entwickelt, mit dem sich die optimale Liste der Parameter für die Untersuchung eines bestimmten Hyporheons auswählen läßt. Der Tendenz in der Fließgewässer-Ökologie, immer neue Konzepte zu entwickeln, die allgemeingültig sein sollen, wurde das Konzept vom individuellen Charakter von Fließgewässer-Ökosystemen entgegengestellt.

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.