Beschreibung
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 wünschenswerte Kenntnisse sind im Anhang aufgeführt), und andererseits werden neben der allgemeinen Theorie neueste Ergebnisse dargestellt. Nach Durcharbeiten dieses Buches ist ein Student in der Lage, Originalliteratur über stochastische Automaten zu lesen und Forschungsprobleme zu formulieren und anzu greifen. Anregungen hierzu findet man außer 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.
Autorenporträt
Inhaltsangabe1. 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.
Herstellerkennzeichnung:
Springer Vieweg in Springer Science + Business Media
Abraham-Lincoln-Straße 46
65189 Wiesbaden
DE
E-Mail: juergen.hartmann@springer.com
