Generalisierte Berechnungen in iterativen Arrays

Abstract

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.

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 untersuchten Sprachklasse 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).

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.

In Kapitel 6 werden alternierende iterative Arrays als Verallgemeinerung der nichtdeterministischen iterativen Arrays eingeführt. Es wird gezeigt, daß sich die meisten Aussagen (Abschlußeigenschaften, Hierarchiesätze, usw.) über nichtdeterministische iterative Arrays auf alternierende iterative Arrays übertragen lassen.

Ein zentraler Punkt ist dabei Lemma 6.6, in dem eine Normalform für alternierende iterative Arrays hergeleitet wird. (Mir ist keine entsprechende Aussage für andere Maschinenmodelle bekannt.) Mit diesem Lemma lassen sich die Ergebnisse aus Kapitel 3 auf alternierende iterative Arrays übertragen (Lemma 6.7 bis 6.11). Allerdings sind die Beweise technisch aufwendiger. Da die meisten Beweise aus den Kapiteln 4 und 5 nur die Hilfmittel aus Kapitel 3 benutzen, übertragen sich nun die Ergebnisse auf alternierende iterative Arrays.