Sprachtheoretische Semantik von Interaktionsausdrücken
Christian Heinlein, Abt. DBIS
Juni 1997
1. Einleitung
Dieser Bericht definiert Interaktionsausdrücke, wie sie in den Berichten „Grundlagen von Interakti-
onsausdrücken“ (UIB 97-09) und “Interaction Expressions −− A Powerful Formalism for Describing
Inter-Workflow Dependencies” (UIB 97-04) beschrieben sind, mittels ihrer sprachtheoretischen Se-
mantik.
Nach einer kurzen Definition der wichtigsten Grundbegriffe werden in Abschnitt 2 zunächst reguläre
Ausdrücke, die eine Teilmenge von Interaktionsausdrücken darstellen, mittels ihrer sprachtheoreti-
schen Semantik definiert. Anschließend wird diese Definition auf elementare Interaktionsausdrücke
erweitert und ein erster Versuch zur Definition von Quantoren unternommen.
Abschnitt 3 zeigt jedoch Schwierigkeiten und Grenzen dieser „traditionellen“ Vorgehensweise auf,
so daß in Abschnitt 4 eine „revidierte“ Definition von Interaktionsausdrücken gegeben wird, die im
wesentlichen auf einer sauberen Trennung von vollständigen und teilweisen Worten basiert.
Alle wesentlichen Definitionen werden jeweils durch Beispiele illustriert, um die abstrakten Konzepte
ein wenig „greifbarer“ zu machen.
2. Traditioneller Ansatz
2.1 Grundbegriffe
Gegeben sei eine Menge Σvon Aktionen (vgl. Grundlagenbericht), die auch Alphabet genannt wird.
Formal ist eine Aktion aein Tupel der Gestalt (a0,a1,...,an)mit n∈IN0, wobei a0der Name und
a1,...,andie (optionalen) Parameter der Aktion sind. Der Einfachheit halber wird eine parameterlo-
se Aktion (a0)jedoch als „Prozedur“ a0und eine parametrisierte Aktion (a0,a1,...,an)als „Funkti-
on“ a0(a1,...,an)geschrieben.
Ein Wort der Länge n (über dem Alphabet Σ) ist ein n-Tupel ‘a1...an’ mit a1,...,an∈Σ(n∈IN0).
Das Wort ‘’ der Länge 0 heißt auch leeres Wort. Die Länge eines Wortes wwird mit |w| bezeichnet.
Die Menge aller Worte über dem Alphabet Σwird mit Σ* bezeichnet.
1
2.2 Reguläre Ausdrücke
Interaktionsausdrücke stellen eine Erweiterung von regulären Ausdrücken dar.1Daher scheint es na-
heliegend, die sprachtheoretische Semantik regulärer Ausdrücke geeignet zu erweitern, um eine ent-
sprechende Semantik für Interaktionsausdrücke zu erhalten.
Die Semantik eines regulären Ausdrucks xwird gewöhnlich als Sprache L(x), d.h. als die Menge al-
ler von diesem Ausdruck akzeptierten Worte, definiert. Für einen beliebigen regulären Ausdruck x
(der nicht gleich der leeren Menge ist, vgl. Fußnote) läßt sich L(x)wie folgt rekursiv definieren:
• Für einen leeren Ausdruck x=
λ
:
L(x)={‘’ }.
• Für einen atomaren Ausdruck x=a:
L(x)={‘a’}.
• Für eine Disjunktion x=y|z:
L(x)=L
(y)∪L(z)={w|w∈L(y)∨w∈L(z)}
.
• Für eine sequentielle Komposition x=y−z:
L(x)=L
(y)L(z)={uv |u∈L(y),v∈L(z)}
.
• Für eine sequentielle Iteration x=y*:
L(x)=L
(y)*= ∞
n=0
∪L(y)n=∞
n=0
∪{u1...un|u1,...,un∈L(y)}
.
Hierbei steht uv =‘u1...umv1...vn’ für die Konkatenation der beiden Worte u=‘u1...um’ und
v=‘v1...vn’. Entsprechend steht u1...unfür die Konkatenation der nWorte u1,...,un(n> 0) bzw.
für das leere Wort (n= 0). Bei den hochgestellten Zahlen handelt es sich hier also nicht um Exponen-
ten, sondern um Indizes. Beachte, daß mit ui(Index unten) Aktionen ∈Σund mit ui(Index oben)
Worte ∈Σ* bezeichnet werden.
Beispiele
a) L(a−b)={uv |u∈L(a),v∈L(b)}={uv |u∈{‘a’},v∈{‘b’}}={‘a’‘b’}={‘ab’}.
b) L(a−b|c)=L
(a−b)∪L(c)={‘ab’}∪{‘c’}={‘ab’, ‘c’}.
c) L((a−b|c)*)=∞
n=0
∪{u1...un|u1,...,un∈L(a−b|c)}=
∞
n=0
∪{u1...un|u1,...,un∈{‘ab’, ‘c’}}={‘’, ‘ab’, ‘c’, ‘ab ab’, ‘abc’, ‘cab’, ‘cc’, . . . }.
2.3 Elementare Interaktionsausdrücke
Die obigen Definitionen lassen sich wie folgt für Interaktionsausdrücke erweitern:
• Für eine Konjunktion x=y&z:
L(x)=L
(y)∩L(z)={w|w∈L(y),w∈L(z)}
.
• Für eine parallele Komposition x=y+z:
L(x)=L
(y)⊗L(z)={w|w∈u⊗v,u∈L(y),v∈L(z)}
.
1... wenn man von der leeren Menge ∅absieht, die formal ein regulärer Ausdruck, jedoch kein Interaktionsausdruck ist.
2
• Für eine parallele Iteration x=y#:
L(x)=L
(y)#= ∞
n=0
∪n
⊗L(y)=∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈L(y)}
.
Hierbei ist u⊗vdefiniert als die Menge aller Worte w, die durch „Mischen“ oder Überlagern der bei-
den Worte uund ventstehen:
u⊗v={u1v1...unvn|n∈IN,u1,v1,...,un,vn∈Σ*, u1...un=u,v1...vn=v}.
Beachte wiederum, daß u1,v1,... nicht einzelne Aktionen, sondern Teilworte von ubzw. vsind, die
ggf. auch leer sein können.
u1⊗...⊗unsteht entsprechend für die Überlagerung der nWorte u1,...,unund kann für n>2
induktiv wie folgt definiert werden:
u1⊗...⊗un=(u1⊗...⊗un−1)⊗{un}.
Für die beiden Grenzfälle n= 0 und n= 1 ist u1⊗...⊗unals {‘’ }bzw. {u1}definiert.
Abgeleitete Operatoren
Die verbleibenden Operatoren, nämlich Synchronisation und Multiplikatoren, lassen sich gemäß ihrer
Definition auf bereits definierte Operatoren zurückführen. Für die Booleschen Multiplikatoren |
und &erhält man z. B.:
L
n
i=m
|xi
=n
i=m
∪L(xi);
L
n
i=m
&xi
=n
i=m
∩L(xi).
Diese Definitionen lassen sich prinzipiell auf den Fall n=∞verallgemeinern:
L
∞
i=m
|xi
=∞
i=m
∪L(xi);
L
∞
i=m
&xi
=∞
i=m
∩L(xi).
Damit hat man prinzipiell die Möglichkeit, auch die beiden Iterationen wie folgt auf „elementarere“
Operatoren zurückzuführen:
x*= ∞
n=0
|n
i=1
−x;
x#= ∞
n=0
|n
i=1
+x.
Wie man leicht sieht, erhält man auf diese Weise dieselben Formeln für L(x*)und L(x#)wie bei den
oben angegebenen „direkten“ Definitionen.
Beispiele
a) L(a+b)=L
(a)⊗L(b)={‘a’}⊗{‘b’}=‘a’⊗‘b’=
{u1v1...unvn|n∈IN,u1...un=‘a’, v1...vn=‘b’}={‘ab’, ‘ba’}.
3
b) L((a+b)#)=∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈L(a+b)}=
∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈{‘ab’, ‘ba’}}={w|wa=wb},
wobei wabzw. wbdie Anzahl der a’s bzw. b’s im Wort wbezeichne.
c) L((a−b)#)=∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈L(a−b)}=
∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈{‘ab’}}={w|wa=wb∧∀i=1,...,|w|: wi
a≥wi
b},
wobei wihier das Präfix der Länge ivon wbezeichne.
Für die Worte wmuß also gelten, daß jedes Präfix von wmindestens so viele a’s wie b’s enthält,
d. h. daß es in wzu jedem bein „zugehöriges“ vorausgehendes ageben muß.
2.4 Quantoren
Durch die Verallgemeinerung der endlichen auf unendliche Boolesche Multiplikatoren wurde bereits
ein erster Schritt unternommen, um die Semantik von Quantoren zu definieren.
Um Quantoren nun auf unendliche Multiplikatoren zurückführen zu können, ist es zweckmäßig, ei-
ne Menge Πeinzuführen, die alle denkbaren Werte
π
enthält, die als aktuelle Parameter von Aktio-
nen auftreten können. Diese Menge läßt sich wie folgt aus der Menge Σaller Aktionen ableiten:
Π=a∈Σ
∪
π
(a),
wobei
π
(a)für eine Aktion a=a0(a1,...,an)als {a1,...,an}definiert ist. Unter der Annahme, daß
diese Menge (höchstens) abzählbar ist −− was für praktische Anwendungen sicherlich realistisch ist −−,
lassen sich ihre Elemente
π
auch in einer bestimmten (willkürlichen) Reihenfolge
π
1,
π
2,... anord-
nen.
Unter Zuhilfenahme dieser Menge Πläßt sich nun der Quantor p
|wie folgt definieren:
p
|x(p)=∞
i=1
|x(
π
i).
Schwierigkeiten bereitet jedoch der Quantor p
+. Die rein formale Umformung
p
+x(p)=∞
i=1
+x(
π
i)
stellt natürlich keine Definition dar, da die Bedeutung eines unendlichen Multiplikators ∞
i=1
+bisher
nicht definiert wurde. Gerade diese Definition erweist sich jedoch als schwierig.
Zum Vergleich betrachte man die Definition einer unendlichen Reihe s=∞
i=1
Σsi, die intuitiv „ein-
fach“ eine Summe mit unendlich vielen Gliedern darstellt, formal jedoch als Grenzwert einer Folge
von endlichen Summen definiert werden muß:
s=n→∞
lim n
i=1
Σsi.
Die Tatsache, daß dieser Grenzwert u. U. gar nicht existiert und der Wert der unendlichen Reihe damit
undefinert ist, macht klar, daß „unendliche Ausdrücke“ nicht immer sinnvoll definiert werden können.
4
In Analogie zur Definition einer unendlichen Reihe werden unendliche Multiplikatorausdrücke und
Quantoren später ebenfalls mit Hilfe von Grenzwerten definiert. Zuvor sollen jedoch einige Schwie-
rigkeiten und Grenzen der bisher definierten Semantik aufgezeigt werden.
3. Schwierigkeiten und Grenzen des traditionellen Ansatzes
3.1 Vollständige versus unvollständige Worte
Beim traditionellen Worterkennungsproblem ist die Frage zu beantworten, ob ein gegebenes Wort w
mit einer bestimmten Länge nin der Sprache L(x)enthalten ist, die durch einen gegebenen Ausdruck
(oder eine Grammatik) xerzeugt wird. So muß beispielsweise ein Compiler für eine Programmier-
sprache (unter anderem) entscheiden, ob ein ihm vorgelegtes Programm korrekt ist oder nicht.
Im Kontext von Interaktionsausdrücken liegt jedoch typischerweise keine vollständige Folge von Ak-
tionen vor, die nachträglich auf Korrektheit überprüft werden soll. Vielmehr werden Aktionen suk-
zessive ausgeführt, und es muß zu jedem Zeitpunkt die Frage beantwortet werden, welche Aktionen
im nächsten Schritt zulässig sind. Da eine einmal begonnene Aktionsfolge prinzipiell jederzeit fort-
gesetzt werden kann, kann man konsequenterweise auch keine Aussage über ihre Länge machen. (Es
gibt kein End of file wie bei einer Datei, das anzeigt, daß das Programm hier zu Ende ist.) Somit ist
der traditionell in Automaten gebräuchliche Begriff des Endzustands in diesem Kontext bedeutungs-
los: Die Menge der Endzustände (oder akzeptierenden Zustände) ist entweder leer oder gleich der
Menge aller Zustände.
Diese unterschiedliche Sichtweise sollte sich auch in der Semantik von Interaktionsausdrücken wider-
spiegeln. Beispielsweise sollte ein Ausdruck wie (a−b)* nicht nur die Worte ‘’, ‘ab’, ‘ab ab’, . . .,
sondern auch die Worte ‘a’, ‘ab a’, ... akzeptieren.
Dies läßt sich prinzipiell dadurch erreichen, daß man nach der Bestimmung der Menge L(x)für
einen gegebenen Ausdruck xdie Menge aller Präfixe
P(x)={u|∃v:uv ∈L(x)}
bestimmt. Wenn dann zu einem bestimmten Zeitpunkt tbereits die Aktionen a1,...,anausgeführt
worden sind, so ist eine weitere Aktion an+1zu diesem Zeitpunkt genau dann zulässig, wenn das Wort
‘a1...anan+1’ in der Menge P(x)enthalten ist.
3.2 Unerfüllbare Teilausdrücke
Intuitiv −− insbesondere wenn man mit der Theorie der formalen Sprachen nicht vertraut ist −− würde
man vermutlich erwarten, daß ein Ausdruck der Gestalt x=a−yim ersten Schritt die Aktion aak-
zeptiert, unabhängig davon, wie der Teilausdruck ybeschaffen ist. In den „meisten“ Fällen trifft dies
auch zu, denn es gilt ja:
L(x)=L
(a−y)=L
(a)L(y)={‘a’w|w∈L(y)}
.
Da alle Worte aus L(x)mit abeginnen, gilt offensichtlich ‘a’∈P(x),d.h.awird als erste Aktion
akzeptiert −− sofern es überhaupt Worte in L(x)gibt! Andernfalls, d. h. wenn L(x)=∅ist, so ist auch
P(x)={u|∃v:uv ∈L(x)}=∅, und der Ausdruck xakzeptiert −− im Gegensatz zur gerade erwähn-
ten „intuitiven Semantik“ −− überhaupt keine Aktionen! Dieser Fall tritt hier genau dann ein, wenn
L(y)=∅ist, was z.B. für y=b&coder auch y=b−c@c−bzutrifft.
5
3.3 Quantoren
Ein ähnliches Problem ergibt sich im Zusammenhang mit Quantoren. Intuitiv sollte der Ausdruck
x=p
+a(p)beliebige Folgen von a(p)’s (mit paarweise verschiedenen Werten von p) akzeptieren. Da
die Menge der möglichen Werte von pjedoch potentiell unendlich groß ist, ist intuitiv ebenso ein-
leuchtend, daß es wohl keine endliche Folge von Aktionen gibt, die diesen Ausdruck vollständig
erfüllt. Somit wäre auch hier L(x)=P
(x)=∅, und der Ausdruck würde nichts akzeptieren.
3.4 Ausweg
Das zuletzt genannte Problem ließe sich prinzipiell durch die Einführung unendlicher Worte lösen,
das Dilemma im Zusammenhang unerfüllbarer Teilausdrücke jedoch nicht.
Beiden Problemen liegt jedoch eine gemeinsame Ursache zugrunde −− die Präfixbildung wird unter
Umständen „zu spät“ durchgeführt: Wenn L(x)=∅ist, dann ist auch P(x)=∅, obwohl der
Ausdruck xintuitiv u. U. gewisse Teilworte akzeptieren sollte.
Andererseits darf die Präfixbildung auch nicht „zu früh“ erfolgen. Würde man sie beispielsweise
auf jeden Teilausdruck einzeln anwenden, d. h. letztlich die Definition L(a)={‘a’}durch
L(a)={‘’, ‘a’}ersetzen, so ergäbe sich z.B.
L(a−b)={uv |u∈L(a),v∈L(b)}={uv |u∈{‘’, ‘a’},v∈{‘’, ‘b’}}=
{‘’, ‘b’, ‘a’, ‘ab’},
was natürlich ebenfalls jeder Intuition widerspricht.
Der Ausweg aus diesem Dilemma besteht darin, für jeden Ausdruck xsowohl eine Präfix-basierte als
auch eine auf vollständigen Worten basierende Definition zu geben und diese geeignet zu kombinie-
ren. Dies ist Gegenstand des folgenden Abschnitts.
4. Teilwortorientierte Semantik
Wie bereits angedeutet, wird in diesem Abschnitt für jeden Ausdruck xsowohl eine Menge C(x)der
von diesem Ausdruck akzeptierten vollständigen Worte (complete words) als auch eine Menge P(x)
der von ihm akzeptierten Teilworte (partial words bzw. Präfixe) definiert. Durch eine geeignete „Ver-
flechtung“ der Definitionen wird sichergestellt, daß die Präfixbildung weder „zu früh“ noch „zu spät“
durchgeführt wird und die resultierende Semantik somit dem im Grundlagenbericht vorgestellten in-
tuitiven Ausführungsmodell von Interaktionsausdrücken entspricht bzw. dieses präzisiert.
4.1 Basisoperatoren
Für einen Interaktionsausdruck xwerden die Mengen C(x)und P(x)wie folgt definiert:
• Für einen leeren Ausdruck x=
λ
:
C(x)={‘’ };
P(x)={‘’ }.
• Für einen atomaren Ausdruck x=a:
C(x)={‘a’};
P(x)={‘’, ‘a’}.
6
• Für eine Disjunktion x=y|z:
C(x)=C
(y)∪C(z)={w|w∈C(y)∨w∈C(z)}
;
P(x)=P
(y)∪P(z)={w|w∈P(y)∨w∈P(z)}
.
• Für eine Konjunktion x=y&z:
C(x)=C
(y)∩C(z)={w|w∈C(y),w∈C(z)}
;
P(x)=P
(y)∩P(z)={w|w∈P(y),w∈P(z)}
.
• Für eine sequentielle Komposition x=y−z:
C(x)=C
(y)C(z)={uv |u∈C(y),v∈C(z)}
;
P(x)=P
(y)∪C(y)P(z)=P
(y)∪{uv |u∈C(y),v∈P(z)}
.
• Für eine sequentielle Iteration x=y*:
C(x)=C
(y)*= ∞
n=0
∪C(y)n=∞
n=0
∪{u1...un|u1,...,un∈C(y)}
;
P(x)=C
(y)*P
(y)=∞
n=0
∪C(y)nP(y)=∞
n=0
∪{u1...un+1|u1,...,un∈C(y),un∈P(y)}
.
• Für eine parallele Komposition x=y+z:
C(x)=C
(y)⊗C(z)={w|w∈u⊗v,u∈C(y),v∈C(z)}
;
P(x)=P
(y)⊗P(z)={w|w∈u⊗v,u∈P(y),v∈P(z)}
.
• Für eine parallele Iteration x=y#:
C(x)=C
(y)#= ∞
n=0
∪n
⊗C(y)=∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈C(y)}
;
P(x)=P
(y)#= ∞
n=0
∪n
⊗P(y)=∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈P(y)}
.
Man beachte, daß die Definitionen für C(x)und P(x)weitgehend „unabhängig“ voneinander sind; le-
diglich bei den sequentiellen Operatoren tritt (erwartungsgemäß) ein Querbezug auf.
Beachte außerdem, daß die Definitionen für C(x)mit den alten Definitionen für L(x)übereinstim-
men.
Beispiele
a) P(a−b)=P
(a)∪{uv |u∈C(a),v∈P(b)}={‘’, ‘a’}∪{uv |u∈{‘a’},v∈{‘’, ‘b’}}=
{‘’, ‘a’}∪{‘a’, ‘ab’}={‘’, ‘a’, ‘ab’}.
b) P(a+b)=P
(a)⊗P(b)={‘’, ‘a’}⊗{‘’, ‘b’}=
(‘’ ⊗‘’)∪(‘’ ⊗‘b’)∪(‘a’⊗‘’)∪(‘a’⊗‘b’)={‘’ }∪{‘b’}∪{‘a’}∪{‘ab’, ‘ba’}=
{‘’, ‘a’, ‘b’, ‘ab’, ‘ba’}.
c) P((a−b)*)=∞
n=0
∪{u1...un+1|u1,...,un∈C(a−b),un+1∈P(a−b)}=
∞
n=0
∪{u1...un+1|u1,...,un∈{‘ab’},un+1∈{‘’, ‘a’, ‘ab’}}=
{‘’, ‘a’, ‘ab’, ‘ab a’, ‘ab ab’, . . . }.
d) P((a−b)#)=∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈P(a−b)}=
∞
n=0
∪{w|w∈u1⊗...⊗un,u1,...,un∈{‘’, ‘a’, ‘ab’}}={w|∀i=1,...,|w|: wi
a≥wi
b}.
e) C(b&c)=C
(b)∩C(c)={‘b’}∩{‘c’}=∅;
P(b&c)=P
(b)∩P(c)={‘’, ‘b’}∩{‘’, ‘c’}={‘’ }.
7
f) C(a−(b&c)) ={uv |u∈C(a),v∈C(b&c)}={uv |u∈{‘a’},v∈∅}=∅;
P(a−(b&c)) =P
(a)∪{uv |u∈C(a),v∈P(b&c)}=P
(a)∪{uv |u∈{‘a’},v∈{‘’ }}=
{‘’, ‘a’}∪{‘a’}={‘’, ‘a’}=P
(a).
4.2 Monotonieregeln
Aus den genannten Definitionen folgen unmittelbar die folgenden „Monotonieregeln“ für beliebige
Ausdrücke x,yund z:
a) ‘’ ∈P(x);
b) P(y−z)⊃P(y);
c) C(y−z)⊃C(y)⇔‘’ ∈C(z);
d) P(y+z)⊃P(y);
e) C(y+z)⊃C(y)⇔‘’ ∈C(z).
Beweis
a) Rekursiv durch Anwenden der Definitionen.
b) Unmittelbar aus der Definition von P(y−z).
c) Falls ‘’ ∈C(z), so folgt aus der Definition von C(y−z):
C(y−z)⊃{uv |u∈C(y),v=‘’}={u|u∈C(y)}=C
(y).
Falls ‘’ ∉C(z), wähle ein Wort u∈C(y)mit minimaler Länge l. Aus der Definition von
C(y−z)folgt zusammen mit ‘’ ∉C(z), daß alle Worte w∈C(y−z)eine Länge größer als lha-
ben. Da unur die Länge lhat, muß somit u∉C(y−z)gelten, woraus die Behauptung
C(y−z)⊃
/C(y)folgt.
d) Wegen (a) gilt ‘’ ∈P(z), und somit folgt ähnlich wie bei (c):
P(y+z)⊃{w|w∈u⊗v,u∈P(y),v=‘’}={w|w∈{u},u∈P(y)}=P
(y).
e) Analog zu (c).
4.3 Multiplikatoren
Endliche Multiplikatoren
Endliche Multiplikatoren werden gemäß ihrer Definition auf Basisoperatoren zurückgeführt:
n
∼x=x∼...∼x(n-mal x,n∈IN);
n
∼x=
λ
für n≤0;
n
k=m
∼xk=xm∼...∼xn(m,n∈ZZ).
Hierbei steht ∼für einen der binären Basisoperatoren −,+, | oder &.
8
Unendliche Multiplikatoren
Die Semantik unendlicher Multiplikatoren wird durch Grenzwerte von Mengenfolgen definiert.
Eine Folge (Mn)∞
n=1 von Mengen Mnhat hierbei den Grenzwert
•n→∞
lim Mn=∞
n=n0
∪Mn={v|∃n≥n0:v∈Mn},
falls die Folge (Mn)ab einem bestimmten n0∈IN monoton wachsend ist, d. h. falls Mn+1⊃Mnfür
alle n≥n0gilt;
•n→∞
lim Mn=∞
n=n0
∩Mn={v|∀n≥n0:v∈Mn},
falls die Folge (Mn)ab einem bestimmten n0∈IN monoton fallend ist, d.h. falls Mn+1⊂Mnfür al-
le n≥n0gilt;
•n→∞
lim Mn=∅,
falls die Folge (Mn)nicht monoton ist, d.h. falls es kein n0∈IN gibt, ab dem die Folge (Mn)mono-
ton wachsend oder monoton fallend ist.
Für einen Ausdruck x=∞
i=1
∼ximit ∼∈{|, &,−,+}werden die Mengen C(x)und P(x)„abstrakt“ wie
folgt definiert:
C(x)=n→∞
lim C(yn),
P(x)=n→∞
lim P(yn),
mit yn=n
i=1
∼xi.
Im folgenden wird für die einzelnen Operatoren diskutiert, wie diese Grenzwerte konkret zu interpre-
tieren sind.
Disjunktion
Für eine unendliche Disjunktion x=∞
i=1
|xi,d.h.yn=n
i=1
|xigilt:
C(yn)=C
n
i=1
|xi
=n
i=1
∪C(xi),
und somit für alle n≥1:
C(yn+1)=C
(yn)∪C(xn+1)⊃C(yn),
d. h. die Mengenfolge (C(yn)) ist ab n0= 1 monoton wachsend, woraus folgt:
C(x)=n→∞
lim C(yn)=∞
n=1
∪C(yn)=∞
n=1
∪n
i=1
∪C(xi)=∞
i=1
∪C(xi).
Ganz analog ergibt sich auch:
P(x)=∞
i=1
∪P(xi).
9
Konjunktion
Dual zur Disjunktion ergibt sich für eine unendliche Konjunktion x=∞
i=1
&xi:
C(x)=∞
i=1
∩C(xi);
P(x)=∞
i=1
∩P(xi).
Kompositionen
Für eine unendliche sequentielle oder parallele Komposition x=∞
i=1
±xi,d.h.yn=n
i=1
±xifolgt aus der
Monotonieregel (b) bzw. (d) für alle n≥1:
P(yn+1)=P
(yn±xn+1)⊃P(yn),
d. h. die Mengenfolge (P(yn)) ist ab n0= 1 monoton wachsend. Somit gilt:
P(x)=n→∞
lim P(yn)=∞
n=1
∪P(yn).
Falls es außerdem ein n0∈IN gibt, so daß C(xi)für alle i≥n0das leere Wort ‘’ enthält −− d. h. wenn
nur endlich viele C(xi)das leere Wort nicht enthalten −−, so gelten die gleichen Überlegungen auf-
grund der Monotonieregel (c) bzw. (e) auch für die Mengenfolge (C(yn)) (für n≥n0), und es gilt:
C(x)=n→∞
lim P(yn)=∞
n=n0
∪C(yn).
Andernfalls, d.h. wenn unendlich viele C(xi)das leere Wort nicht enthalten, ist die Mengenfolge
(C(yn)) auf jeden Fall nicht monoton wachsend. Wenn sie (ab einem bestimmten n0) monoton fallend
wäre, wäre der Grenzwert C(x)als unendlicher Durchschnitt ∞
n=n0
∩C(yn), andernfalls als leere Menge
zu interpretieren.
Da jedoch unendlich viele Teilausdrücke xinur durch Worte positiver Länge erfüllbar sind, würde
man intuitiv in keinem dieser beiden Fälle erwarten, daß der Gesamtausdruck xdurch ein Wort endli-
cher Länge erfüllt werden kann. Das Resultat des unendlichen Durchschnitts sollte also ebenfalls
gleich der leeren Menge sein, so daß sich die Frage erübrigt, unter welchen Umständen die Mengen-
folge (C(yn)) monoton fallend ist.
Zum Beweis dieser Vermutung betrachte man die folgende Funktion l, die einem beliebigen
Ausdruck zdie minimale Länge seiner vollständigen Worte zuordnet:
l(z)= min {|w||w∈C(z)}
.
Offensichtlich erfüllt ldie beiden folgenden Aussagen:
l(z)≥1, wenn ‘’ ∉C(z);
l(y±z)=l(y)+l(z).
Daraus folgt:
l(yn)=l
n
i=1
±xi
=n
i=1
Σl(xi)→∞für n→∞,
da l(xi)≥1 für unendlich viele igilt. Wenn es nun ein Wort u∈∞
n=n0
∩C(yn)gäbe, so würde für jedes
n≥n0gelten:
10
u∈C(yn)⇒l(yn)= min {|w||w∈C(yn)}≤|u|,
d. h. l(yn)wäre durch |u| beschränkt, was einen Widerspruch zu l(yn)→∞darstellt.
Zusammenfassend gilt für eine unendliche sequentielle oder parallele Komposition x=∞
i=1
±xi:
C(x)=∞
n=n0
∪C
n
i=1
±xi
, falls für alle i≥n0gilt: ‘’ ∈C(xi);
C(x)=∅, falls kein derartiges n0∈IN existiert;
P(x)=∞
n=1
∪P
n
i=1
±xi
.
4.4 Quantoren
Nach der Definition unendlicher Multiplikatoren lassen sich nun Quantoren unter Zuhilfenahme der in
Abschnitt 2.4 eingeführten Menge Πeinfach wie folgt definieren:
p
|x(p)=∞
i=1
|x(
π
i);
p
&x(p)=∞
i=1
&x(
π
i);
p
+x(p)=∞
i=1
+x(
π
i).
Rein theoretisch ist diese Definition natürlich auch für die sequentielle Komposition anwendbar. Al-
lerdings würde ihre Bedeutung dann von der Anordnung der Werte
π
iabhängen, was für praktische
Anwendungen natürlich sinnlos ist (vgl. auch Abschnitt 10.6 im Grundlagenbericht).
Der Quantor
p
@wird im Abschnitt 4.5 definiert.
Beispiele
a) C
p
|a(p)
=C
∞
i=1
|a(
π
i)
=∞
i=1
∪C(a(
π
i)) =∞
i=1
∪{‘a(
π
i)’}={‘a(
π
1)’, ‘a(
π
2)’, . . . };
P
p
|a(p)
=P
∞
i=1
|a(
π
i)
=∞
i=1
∪P(a(
π
i)) =∞
i=1
∪{‘’, ‘a(
π
i)’}={‘’, ‘a(
π
1)’, ‘a(
π
2)’, . . . }.
b) C
p
+a(p)
=C
∞
i=1
+a(
π
i)
=∅,
da kein C(a(
π
i)) das leere Wort ‘’ enthält, d. h. unendliche viele C(a(
π
i)) das leere Wort nicht ent-
halten;
P
p
+a(p)
=P
∞
i=1
+a(
π
i)
=∞
n=1
∪P
n
i=1
+a(
π
i)
=
∞
n=1
∪{‘w1...wn’|{w1,...,wn}={a(
π
1),...,a(
π
n)}}={a(
π
1),a(
π
2),...}*.
11
c) C
p
+a(p)−b
=
uv |u∈C
p
+a(p)
,v∈C(b)
={uv |u∈∅,v∈{‘b’}}=∅;
P
p
+a(p)−b
=P
p
+a(p)
∪
uv |u∈C
p
+a(p)
,v∈P(b)
=
P
p
+a(p)
∪{uv |u∈∅,v∈{‘’, ‘b’}}=P
p
+a(p)
∪∅=P
p
+a(p)
.
4.5 Synchronisation
Obwohl die Synchronisation aufgrund ihrer großen praktischen Bedeutung im Grundlagenbericht wie
ein Basisoperator behandelt wird, ist sie aus theoretischer Sicht ein abgeleiteter Operator, der wie
folgt auf Basisoperatoren zurückgeführt werden kann.
Alphabet eines Ausdrucks
Der Begriff des Alphabets eines Ausdrucks wurde im Grundlagenbericht informell als die Menge al-
ler Aktionen dieses Ausdrucks definiert.
Formal läßt sich das Alphabet
α
(x)eines Ausdrucks xwie folgt rekursiv definieren:
• Für einen atomaren Ausdruck x=a:
α
(x)={a}.
• Für einen Ausdruck der Gestalt x=y* oder x=y#:
α
(x)=
α
(y).
• Für einen Ausdruck der Gestalt x=y∼zmit einem beliebigen binären Operator ∼:
α
(x)=
α
(y)∪
α
(z).
• Für einen Ausdruck der Gestalt x=∞
i=1
∼xi:
α
(x)=∞
i=1
∪
α
(xi).
Binäre Synchronisation
Bereits im Grundlagenbericht wurde der Ausdruck y@zdefiniert als:
y@z=(y+(z1|z2|...
)*)&(z+(y1|y2|...
)*),
wobei {z1,z2,...}=
α
(z)\
α
(y)und {y1,y2,...}=
α
(y)\
α
(z)gilt.
Endliche Multiplikatoren
Ein endlicher Multiplikator-Ausdruck
n
@xoder
n
k=m
@x(k)kann wie in Abschnitt 4.3 auf den binären
Operator @zurückgeführt werden.
12
Unendliche Multiplikatoren
Die Semantik einer unendlichen Synchronisation x=∞
i=1
@xiwird schrittweise wie folgt definiert.
Für i∈IN sei die Menge Aidefiniert als das Komplement des Alphabets des Teilausdrucks xibzgl.
des Alphabets des Gesamtausdrucks x, d. h.:
Ai=
α
(x)\
α
(xi).
Wie üblich bezeichne dann A*
idie Menge aller Worte über der Menge Ai, d. h.:
A*
i={‘w1...wn’|w1,...,wn∈Ai,n∈IN0}.
Die Menge Cibzw. Pientstehe durch Überlagern dieser Worte mit den vom Teilausdruck xiakzeptier-
ten vollständigen bzw. teilweisen Worten:
Ci=C
(xi)⊗A*
i;
Pi=P
(xi)⊗A*
i.
Cibzw. Pienthält somit genau die (vollständigen bzw. teilweisen) Worte, die der Ausdruck xi„im
Kontext“ der Synchronisation xakzeptiert. (Ein Teilausdruck einer Synchronisation soll ja die Aktio-
nen, die nur in anderen Teilausdrücken vorkommen, zu jedem Zeitpunkt akzeptieren.)
Nach diesen Vorbereitungen werden die Mengen C(x)und P(x)dann wie folgt definiert:
C(x)=∞
i=1
∩Ci;
P(x)=∞
i=1
∩Pi.
Quantoren
Der Quantor
p
@läßt sich nun analog zu den übrigen Quantoren definieren:
p
@x(p)=∞
i=1
@x(
π
i).
Beispiele
a) x=a−b@a−c=a−b+c*&a−c+b*;
C(x)=C
(a−b+c*)∩C(a−c+b*)=(C(a−b)⊗C(c)*)∩(C(a−c)⊗C(b)*)=
({ ‘ab’}⊗{‘c’n|n∈IN0}) ∩({ ‘ac’}⊗{‘b’n|n∈IN0}) =
{‘c’n1‘a’‘c’n2‘b’‘c’n3|n1,n2,n3∈IN0}∩{‘b’n1‘a’‘b’n2‘c’‘b’n3|n1,n2,n3∈IN0}=
{‘abc’, ‘ac b’}.
b) x=
p
@x(p)mit x(p)=a(p)−b;
x=∞
i=1
@x(
π
i)=∞
i=1
@ximit xi=x(
π
i)=a(
π
i)−b;
α
(xi)={a(
π
i),b};
α
(x)=
α
∞
i=1
@xi
=∞
i=1
∪
α
(xi)=∞
i=1
∪{a(
π
i),b}={a(
π
)|
π
∈Π}∪{b};
Ai=
α
(x)\
α
(xi)={a(
π
)|
π
∈Π,
π
≠
π
i};
Ci=C
(xi)⊗A*
i={‘a(
π
i)b’}⊗A*
i;
13
Pi=P
(xi)⊗A*
i={‘’, ‘a(
π
i)’, ‘a(
π
i)b’}⊗A*
i;
C(x)=∞
i=1
∩Ci=∅, denn:
Für jedes Wort w∈Cigilt, daß a(
π
i)in wvor bauftritt. Somit müßte in einem Wort
w∈C(x)=∞
i=1
∩Cijedes a(
π
i)vor bauftreten, was für endliche Worte nicht möglich ist.
P(x)=∞
i=1
∩Pi={‘a(p1)...a(pn)’|p1,..., pn∈Πpaarweise verschieden, n∈IN0}.
5. Ausblick
Die in diesem Bericht vorgestellte Semantik dient natürlich einerseits dazu, die präzise Bedeutung ei-
nes einzelnen Ausdrucks festzulegen. Auf der anderen Seite kann sie dazu verwendet werden, Aussa-
gen über die Gleichheit oder Äquivalenz zweier Ausdrücke zu machen:
Zwei Ausdrücke xund yheißen genau dann gleich oder äquivalent, wenn C(x)=C
(y)und
P(x)=P
(y)gilt.
Beispielsweise kann man zeigen, daß die Ausdrücke x#, x*#,x#* und x# # alle äquivalent sind.
Ebenso sind aber auch p
+a(p)und p
+a(p)−bäquivalent (vgl. Beispiele in Abschnitt 4.4), obwohl ihr
Alphabet verschieden ist! Da das Alphabet eines Ausdrucks jedoch von Bedeutung sein kann, wenn
er als Teilausdruck einer Synchronisation verwendet wird, definieren wir noch einen zweiten Gleich-
heitsbegriff:
Zwei Ausdrücke xund yheißen genau dann absolut gleich oder absolut äquivalent, wenn
C(x)=C
(y),P
(x)=P
(y)und
α
(x)=
α
(y)gilt.
Nur wenn zwei Teilausdrücke absolut äquivalent sind, kann man den einen gefahrlos durch den ande-
ren ersetzen, ohne dadurch die Bedeutung des Gesamtausdrucks zu verändern.
Aussagen über die Äquivalenz von Ausdrücken können u. U. für ihre (effiziente) Implementierung
nützlich sein. In Analogie zur Anfrageoptimierung in (relationalen) Datenbanksystemen könnte man
auch für Interaktionsausdrücke versuchen, einen Algorithmus zu formulieren, der versucht, zu einem
vorgegebenen Ausdruck einen möglichst effizient implementierbaren äquivalenten Ausdruck zu fin-
den. Die aus dem DB-Bereich bekannten Probleme (insbesondere die Frage der sinnvollen Begren-
zung des „Suchraums“) dürften sich jedoch übertragen, so daß diese Aufgabe sicherlich sehr schwie-
rig zu lösen sein dürfte.
Äquivalenzregeln können aber auch dazu benutzt werden, den Aufwand für eine Implementierung zu
reduzieren. So wird in der derzeit entwickelten Implementierung beispielsweise die parallele Iteration
wie folgt auf einen Quantorausdruck zurückgeführt:
x#= p
+(x|
λ
),
wobei pein „anonymer“ Parameter ist, der im Ausdruck xnicht vorkommt.
14
