Generalisierte Berechnungen in iterativen Arrays

dc.contributor.authorKlein, Andreas
dc.date.accessioned2023-02-09T15:31:39Z
dc.date.available2000-01-12T23:00:00Z
dc.date.available2023-02-09T15:31:39Z
dc.date.issued1999
dc.description.abstractIn 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.de_DE
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-2023
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/10052
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-9436
dc.language.isode_DEde_DE
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subject.ddcddc:004de_DE
dc.titleGeneralisierte Berechnungen in iterativen Arraysde_DE
dc.typedoctoralThesisde_DE
dcterms.dateAccepted1999-12-20
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id202
local.opus.instituteInstitut für Informatikde_DE
thesis.levelthesis.doctoralde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
d000003.pdf
Größe:
695.55 KB
Format:
Adobe Portable Document Format