Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-2023
URL: http://geb.uni-giessen.de/geb/volltexte/2000/202/


Generalisierte Berechnungen in iterativen Arrays

Klein, Andreas


pdf-Format: Dokument 1.pdf (696 KB)
ps-Format: Dokument 1.ps (874 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Sprache: Deutsch
Tag der mündlichen Prüfung: 20.12.1999
Erstellungsjahr: 1999
Publikationsdatum: 13.01.2000
Kurzfassung auf Deutsch: 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.