Stochastische Automaten

ISBN-13: 9783519000068 / Niemiecki / Miękka / 1971 / 186 str.

V. Claus

Opis

Dieses Buch entstand aus einer Vorlesung, die der Autor unter dem gleichen Titel im Wintersemester 70/71 an der Universitat des Saarlandes hielt. Wahrend es in der Vor lesung primar um die Vermittlung der Theorie ging, treten daneben in diesem Buch weitere Ziele. Eines dieser Ziele besteht darin, bereits Studenten des dritten und vierten Semesters einen Einblick in Fragen der aktuellen Forschung zu geben. Daher werden einerseits nur die Kenntnisse der mathematischen Grundvorlesungen (insbesondere der linearen Algebra) sowie eine Vorstellung der Begriffe Wahrscheinlichkeit und bedingte Wahrschein lichkeit vorausgesetzt (weitere wunschenswerte Kenntnisse sind im Anhang aufgefuhrt), und andererseits werden neben der allgemeinen Theorie neueste Ergebnisse dargestellt. Nach Durcharbeiten dieses Buches ist ein Student in der Lage, Originalliteratur uber stochastische Automaten zu lesen und Forschungsprobleme zu formulieren und anzu greifen. Anregungen hierzu findet man ausser im Text z.B. in den Originalarbeiten 1], SJ, 13J, 20J, 27J, 43J, 49J, 71J. Ein weiteres Ziel stellt die Motivierung der Theorie dar, z.B. die Angabe konkreter Problemstellungen, die sich durch stochastische Automaten beschreiben lassen. Daher sind der eigentlichen Theorie Beispiele (siehe 1.2.) vorangestellt, die dem Verstandnis der Definitionen und der Theorie dienen."

Spis treści

1. Einführung.- 1.1. Einleitung.- 1.2. Beispiele.- 1.2.1. Zustände.- 1.2.2. Nervennetze.- 1.2.3. Lernmodell.- 1.2.4. Nachrichtenübertragung.- 1.2.5. Verkehrsregelung.- 1.3. Stochastische Automaten.- 1.3.1. Definitionen.- 1.3.2. Darstellung durch Matrizen.- 1.3.3. Äquivalenz.- 2. Reduktionen.- 2.1. Reduzierte Automaten.- 2.1.1. Definition.- 2.1.2. Konstruktion reduzierter Automaten.- 2.1.3. Entscheidbarkeit der Z-Äquivalenz.- 2.1.4. Gegenbeispiele.- 2.1.5. Die Matrix HA.- 2.2. Minimale Automaten.- 2.2.1. Definition.- 2.2.2. Konstruktion minimaler Automaten.- 2.2.3. Entscheidbarkeit der Äquivalenz.- 2.2.4. Das Beispiel von Even.- 2.2.5. Starkreduzierte Automaten.- 2.2.6. Geometrische Interpretation.- 2.3. Überdeckungen (Stochastische Homomorphie).- 2.3.1. Definition.- 2.3.2. Überdeckungen und stochast.Homomorphie.- 2.3.3. Verträglichkeit mit HA.- 2.3.4. Zwei Probleme.- 2.4. Homomorphismen.- 2.4.1. Definition.- 2.4.2. Homomorphismen und Z-Äquivalenz.- 2.4.3. Epimorph-reduzierte Automaten.- 2.4.4. Schwache Homomorphismen.- 2.5.Spezielle Automaten.- 2.5.1. Observable Automaten.- 2.5.2. Observable Erweiterungen.- 2.5.3. Z-determinierte Automaten.- 2.5.4. Y-determinierte Automaten.- 2.5.5. Determinierte Automaten.- 2.5.6. Mealy- und Moore-Automaten.- 3. Stochastische Sprachen.- 3.1. Stochastische Akzeptoren.- 3.1.1. Einleitung und Definition.- 3.1.2. Definition der stochastischen Sprachen.- 3.1.3. m-adische Akzeptoren.- 3.1.4. Normierungssätze.- 3.2. Isolierte Schnittpunkte.- 3.2.1. Definition.- 3.2.2. Der Satz von Rabin.- 3.2.3. Stabilitätsproblem und aktuelle Akzeptoren.- 3.3. Verallgemeinerte Akzeptoren.- 3.3.1. Definition.- 3.3.2. Der Satz von Turakainen.- 3.3.3. Eine Charakterisierung der stochastischen Sprachen.- 3.4. Abschlußeigenschaften.- 3.4.1. Zusammenfassung.- 3.4.2. Spiegelung.- 3.4.3. Durchschnitt und Vereinigung mit regulären Mengen.- 3.4.4. Komplement.- 3.4.5. Vereinigung, Durchschnitt, Produkt, Untermonoid.- 3.4.6. Homomorphismen.- 3.4.7. Aufgaben.- 3.4.8. Vergleich mit anderen Sprachhierarchien.- 3.5. Zusammenhänge mit stochastischen Automaten.- 3.5.1. Von einem ESA darstellbare Sprachen.- 3.5.2. Reduktionstheorie.- 4. Realisierbarkeit von Abbildungen.- 4.1. Stochastische Operatoren.- 4.1.1. Definition.- 4.1.2. Realisierbarkeit unbestimmter Operatoren.- 4.1.3. Charakterisierung finiter Realisierbark..- 4.1.4. Eine Rekursionsformel für finitrealisierbare Operatoren.- 4.2. Stochastische Ereignisse.- 4.2.1. Definition.- 4.2.2. Abschlußeigenschaften von SX.- 4.2.3. Beziehungen zu stochastischen Sprachen.- 4.2.4. Entscheidbarkeit.- 4.2.5. Bemerkungen.- Anhang 1: Determinierte Automaten und Akzeptoren.- Anhang 2: Grundlagen der Wahrscheinlichkeitstheorie.- Bezeichnungen.