Grundlagen

In der Arbeit beschränke ich mich auf Spracherkennung. Diese Einschränkung ist nicht wesentlich, da sich viele Algorithmen für Spracherkennung in numerische Algorithmen umwandeln lassen. Ein Algorithmus, der die Sprache
$\{ww \mid w \in \{0,1\}^{*}\}$ erkennt, läßt sich dazu benutzen, das Skalarprodukt zweier Vektoren zu berechnen. Man muß lediglich die elementaren Operationen $\cdot$ und + als Vergleich und ,,und`` interpretieren.

Die Definitionen 2.1 bis 2.12 führen bekannte Tatsachen (von-Neumann-Nachbarschaft, usw.) ein.

In den Definitionen 2.11, 2.14 und 2.16 wird das Modell des iterativen Arrays mit beschränkten Nichtdeterminismus eingeführt. Eingeschränkter Nichtdeterminismus wurde bisher noch nie bei iterativen Arrays untersucht. Da nur Spracherkennung betrachtet wird, haben die iterativen Arrays kein Ausgabeband, sondern eine in akzeptierende und nichtakzeptierende Zustände aufgeteilte Endzustandsmenge.

Zeitbeschränkung und Beschränkung des Nichtdeterminismus werden so definiert, daß die entsprechende Schranke für alle Wahlmöglichkeiten erfüllt sein muß. Dies garantiert, daß die Sprachklasse $\mathscr{L}_{t(n)}(f(n)-\operatorname{NIA})$ für alle Funktionen t,f ,,vernünftig`` (d.h. berechenbar) ist. Dies ist bei den bisherigen Modellen mit eingeschränktem Nichtdeterminismus für Turing-Maschinen nicht der Fall (siehe Bemerkung 2.17 und Anhang B).

Die Sätze 2.15 und 2.18 bringen Beispiele für typische Sprachen, die von nichtdeterministischen iterativen Arrays erkannt werden können. (Das verzögerte Raten eines Zählers Seite 21 ist eine neue Technik. Die anderen Techniken ,,Binärzähler``, ,,FiFo-Schlange``, ,,speichern von Wörtern`` sind von deterministischen iterativen Arrays bekannt.)

In Abschnitt 3.3 wird ein Beschleunigungslemma für die Zeit und ein Reduktionslemma für die Anzahl der nichtdeterministischen Schritte bewiesen. Das Beschleunigungslemma für die Zeit benutzt bekannte Methoden von deterministischen iterativen Arrays. Das Reduktionslemma für die Anzahl der nichtdeterministischen Schritte benutzt dagegen neue Methoden.

Die in Abschnitt 3.4 eingeführten Äquivalenzklassen sind eine Verallgemeinerung des entsprechenden Konzepts von Cole 1966. Daß die Verallgemeinerung ganz entscheidend ist, sieht man am besten an Satz 5.9, in dem Lemma 3.16 benutzt wird, um eine neue Aussage für deterministische iterative Arrays zu beweisen.