id: 01015097
dt: b
an: 01015097
au: Reineke, Henning
ti: Structure and behavior of distributed finite automata. (Struktur und
    Verhalten von verteilten endlichen Automaten.)
so: Oldenburg: Univ. Oldenburg, FB Informatik, viii, 136 p. (1995).
py: 1995
pu: Oldenburg: Univ. Oldenburg, FB Informatik
la: DE
cc: 
ut: distributed finite automata; traces
ci: 
li: 
ab: Summary: Traces sind Verallgemeinerungen von Wörtern auf nebenläufige
    Prozesse: Dem Alphabet wird eine symmetrische und antireflexive
    Unabhängigkeitsrelation auf Zeichen zugeordnet. Wörter sind
    Repräsentanten desselben Traces, wenn sie sich nur in der Reihenfolge
    von aufeinanderfolgenden unabhängigen Zeichen unterscheiden. Viele aus
    der Theorie der formalen Sprachen bekannte Begriffe und Konzepte lassen
    sich ebenso für Traces and Trace-Sprachen formulieren und anwenden. Im
    Jahre 1987 definierte Zielonka mit dem endlichen asynchronen Automaten
    den Typ eines verteilten Automaten zur Erkennung von Trace-Sprachen.
    Die Klasse der erkennbaren Trace-Sprachen ist daher eine
    Verallgemeinerung der Klasse der regulären (Wort-)Sprachen. Obwohl die
    erkennbaren Trace-Sprachen ein vielfältigeres und interessanteres
    Gebiet darstellen als die Klasse der regulären Wortsprachen, scheinen
    sie bisher weniger untersucht worden zu sein. In dieser Arbeit werden
    Teilklassen der erkennbaren Trace-Sprachen durch Betrachtung der
    verteilten Struktur und des nebenläufigen Verhaltens des endlichen
    asynchronen Automaten definiert. In diesem Zusammehang spielen die
    Mechanismen eine besondere Rolle, nach denen die Teilautomaten
    kooperieren. Die definierten Teilklassen werden unabhängig vom
    Automatentyp charakterisiert, so daß sie allgemeine Eigenschaften
    (erkennbaren) nebenläufigen Verhaltens beschreiben. Es werden
    Eigenschaften der Sprachklassen und Beziehungen zwischen den
    Sprachklassen untersucht. Hierbei dient die Unabhängigkeitsrelation
    als Parameter, z.B. stimmen die Teilklassen mit der Klasse der
    erkennbaren Trace-Sprachen bei leerer Unabhängigkeitsrelation
    überein. Drei Teilklassen sind identisch, wenn nur
    präfixabgeschlossene Sprachklassen betrachtet werden. Zielonkas
    Konstruktion eines endlichen asynchronen Automaten zu einer gegebenen
    Trace-Sprache ist ebenso kompliziert wie aufwendig. Von daher ergibt
    sich ein weiteres Motiv für die Betrachtung von Teilklassen der
    erkennbaren Trace-Sprachen. Es zeigt sich jedoch, daß die hier
    definierten Sprachklassen keine einfachere Automatenkonstruktion
    zulassen. Andererseits offenbart die Untersuchung von Zielonkas
    Konstruktionsverfahren eine entscheidende Vereinfachung für erkennbare
    Trace-Sprachen, die auf Alphabeten mit einer speziellen
    Unabhängigkeitsrelation definiert sind. Im Aushang wird das Trace
    Modell einer Fertigungszelle vorgestellt. Das Verhalten wird mit Hilfe
    der hier definierten Begriffe interpretiert.
rv: