Martin Kutrib

Parallele Automaten
 

Volltext des Dokuments: r980002.ps.gz  (395 K)

Report:
Arbeitsgruppe Informatik, Bericht 9401, Februar 1994

Institut:
Arbeitsgruppe Informatik, Universität Giessen, Arndtstr.2, D-35392 Giessen

Erscheinungsjahr:
1994

Inhaltsverzeichnis:
Inhaltsverzeichnis i
1 Vorwort und Einleitung 1
2 Grundlagen 5
2.1 Formale Sprachen 5
2.2 Erzeugendensysteme 7
2.3 Klassische Automatenhierarchie 9
2.3.1 Endliche Automaten 9
2.3.2 Kellerautomaten 11
2.3.3 Linear beschränkte Automaten  13
2.3.4 Turingmaschinen 16
3 Zellularräume und ­automaten 19
3.1 Einführung 19
3.2 Standardisierung von Zellularräumen 25
3.2.1 Rasterreduktion  26
3.2.2 Zeitreduktion 30
3.2.3 Zustandsreduktion 32
3.3 Berechnungsuniversalität 35
3.4 Das Firing Squad Synchronization Problem 38
3.5 Sprachverarbeitung 48
3.5.1 Grundlegendes 49
3.5.2 Unidirektional versus bidirektional 56
3.5.3 Abschlußeigenschaften 62
4 Iterative Arrays 70
4.1 Definitionen 70
4.2 Vergleich mit Zellularräumen 73
4.3 Unvergleichbarkeit der Familien L rt (IA) und L rt (OCA) 74
4.4 Iterative Arrays versus bidirektionale Zellularautomaten 84
5 Keller­Zellularautomaten 87
5.1 Das Modell 87
5.2 Kellernormalisierung und ­kompression 93
5.2.1 Reduktion des Kelleralphabets 93
5.2.2 Reduktion der Kellertiefe 98
5.2.3 Kellernormalisierung 105
5.3 (Nicht­)Akzeptanz spezieller Sprachfamilien 106
5.4 Abschlußeigenschaften 126
5.5 Vergleich mit Zellularräumen 133
5.5.1 Zellularautomaten 133
5.5.2 Eine besondere Sprache 136
Literaturverzeichnis 146

Sprache:
deutsch

Dateiformat:
PostScript (gzip compressed)

Sachgruppe der DNB:
28 Informatik

Eingabedatum:
26.05.1998

Zurück zum Anfang Zur "Giessener Elektronischen Bibliothek"
Fragen und Kommentare an: koordinierung@ub.uni-giessen.de Zuletzt geändert am 17.06.1999