Gefaerbte Graphen auf Algorithmen

7/25/2019 Gefaerbte Graphen auf Algorithmen

1/24

Gefarbte S/T-Systeme

Ermoglichen einekompaktere Darstellungvon S/T-Systemen.

Marken haben unterschiedlicheFarben.Jede Stelle besitzt eineMultimengegefarbter Marken.

Transitionen haben verschiedeneSchaltmodi.

Sabine Kuske (Universitat Bremen,Informatik) Petri-Netze, WS 2015/1016 1 / 24
http://find/


2/24

Endliche Multimengen

In einer Multimenge durfen Elemente mehrfach vorkommen.

Sei A ein endliches Alphabet. EineMultimengeuber A ist eine Abbildung

d: A N,

die jedem Element aus A die Haufigkeit seines Vorkommens zuordnet.Die Multimenge dwird oft auch durch den Ausdruck

cA

d(c) c

notiert.

DieMenge aller Multimengenuber A wird mit MM(A) bezeichnet.

http://find/http://goback/


3/24

Beispiel

Fur A= {a, b, c} wird die Multimenge d={a, b, a} einerseits durch dieAbbildung d beschrieben mit

d(a) = 2d(b) = 1d(c) = 0

und andererseits durch die den Ausdruck

2 a+ 1 b+ 0 c.

http://find/


4/24

Rechnen mit Multimengen

Seien d1 und d2 Multimengenuber A.

Vergleich

d1d2, falls d1(c) d2(c) fur alle cA.

Addition

(d1+d2)(c) =d1(c) +d2(c) fur alle cA.

Subtraktion

(d1 d2)(c) =d1(c) d2(c) fur alle cA,falls d1d2.

http://find/


5/24

Gefarbte S/T-Systeme

Eingefarbtes S/T-Systemuber einer Farbenmenge A ist ein TupelGSTS= (S, T, F, C, W, M0), wobei Folgendes gilt:

(S, T, F) ist ein Netz mit S T =.

C: S T P(A) ordnet jeder Stelle und jeder Transition eine

Menge von Farben zu. P(A) bezeichnet die Potenzmenge von A.W ist eine Abbildung, die jeder Kante eFeine AbbildungW(e) : C(t) MM(C(s)) zuordnet, wobei tdie Transition und s dieStelle von e ist. (W(e) ordnet jeder Farbe von teine Multimenge der

Markenfarben vons

zu.)M0 ist dieAnfangsmarkierung. Sie ordnet jeder Stelle sS eineMultimenge M0(s) MM(C(s)) ihrer Markenfarben zu.



6/24

Die speisenden Philisophen als gefarbtesS/T-System

Eating

Fork1 23 4

Thinking

1 23 4

take lr

id

id

putlr

id

id

mitC(Fork) =C(Eating) =C(Thinking) =C(put) =

C(take) ={1, 2, 3, 4}

id(i) =i fur i= 1, . . . , 4

lr(1) ={1, 4}

lr(2) ={1, 2}lr(3) ={2, 3}lr(4) ={3, 4}

Die Gabeln 1,. . . ,4 sind an ihrem Platz; die Philosophen1,. . . ,4denken.

http://find/


7/24

Markierungen

Markierung

Sei GSTS= (S, T, F, C, W, M0) ein gefarbtes S/T-System.EineMarkierung M von GSTSist eine Abbildung, die jeder Stelle sSeine Multimenge M(s) MM(C(s)) zuordnet.

(M,a)-aktivierte Transition

Sei Meine Markierung, teine Transition und aC(t). Dann heit t(M, a)-aktiviert, falls

M(s) W(s, t)(a)

fur alle s t.

http://find/


8/24

Beispiel

Eating

Fork1 23 4

Thinking

1 23 4

take lr

id

id

putlr

id

id

mit

C(Fork) =C(Eating) =C(Thinking) =C(put) =C(take) ={1, 2, 3, 4}

id(i) =i fur i= 1, . . . , 4

lr(1) ={1, 4}lr(2) ={1, 2}lr(3) ={2, 3}lr(4) ={3, 4}

Die Transition take ist inden Farben 1,2,3 und 4aktiviert.

http://find/


9/24

Schaltverhalten

Schalten einer Transition in gefarbten S/T-Systemen

Eine (M, a)-aktivierte Transitionschaltetvon M nach M, in ZeichenM[t, aM, falls

M(s) =

M(s) W(s, t)(a) fur s t t

M(s) +W(t, s)(a) fur st tM(s) W(s, t)(a) +W(t, s)(a) fur s t t

M(s) sonst

M heit(direkte) Folgemarkierungvon M.

http://find/


10/24

Beispiel

Eating

Fork

1 23 4

Thinking

1 23 4

take lr

id

id

putlr

id

id

[take, 3

Eating

3

Fork

1 4

Thinking

12 4

take lr

id

id

putlr

id

id

Nach dem Schalten von take in der Farbe 3 isst Philosoph 3 mit denGabeln 2 und 3.

http://find/


11/24

Entfaltung gefarbter S/T-Systeme zuS/T-Systemen

Sei GSTS= (S, T, F, C, W, M0) ein gefarbtes S/T-System. DieEntfaltungvon GSTS ist das S/T-System

flt(GSTS) = (S, T, F, W, M0) mit

S ={(s, x)| sS, xC(s)},

T ={(t, y)| tT, yC(t)},

F = {((s, x), (t, y))| (s, t) F, ((W(s, t))(y))(x) >0}

{((t, y), (s, x))| (t, s) F, ((W(t, s))(y))(x) >0},

W((s, x), (t, y)) = ((W(s, t))(y))(x),W((t, y), (s, x)) = ((W(t, s))(y))(x) und

M0(s, x) = (M0(s))(x).



12/24

Beispiel 1

Die Entfaltung von

11 2s tf

mit C(s) ={1, 2}, C(t) ={rot, blau},f(rot) ={1, 1, 2} und f(blau) ={1}

liefert das S/T-System

(s, 1)

(s, 2)

(t, rot)2

(t, blau)

http://find/


13/24

Beispiel 2

Die Entfaltung von

Eating

3

Fork

1 4

Thinking

12 4

take lr

id

id

putlr

id

id

mit C(Fork) =C(Eating) =C(Thinking) =C(put) =C(take) ={1, 2, 3, 4}

id(i) =i fur i= 1, . . . , 4

lr(1) ={1, 4}

lr(2) ={1, 2}lr(3) ={2, 3}lr(4) ={3, 4}

http://find/


14/24

liefert das S/T-System

(take,4)

(Eating,4)

(Thinking,4)

(put,4)

(Fork,4)

(put,1)

(Thinking,1)

(take,1)

Eating,1)

(Fork,1)

(put,2)

(Thinking,2)

(take,2)

(Eating,2)

(Fork,2)

(put,3)

(Thinking,3)

(take,3)

(Eating,3)

(Fork,3)

http://find/


15/24

Faltung von S/T-Systemen zugefarbten S/T-Systemen

Sei STS= (S, T, F, W, M0) ein S/T-System.Sei X ={S1, . . . Sk} mit SiS fur i= 1, . . . , k,

ki=1Si =S und

Si Sj= fur i=j.

Sei Y ={T1, . . . Tl} mit TiT fur i= 1, . . . , l,l

i=1Ti =T und

Ti Tj= fur i=j.Dann ist dieFaltungvon STS bzgl. X und Y das gefarbte S/T-Systemctr(STS) = (S, T,F, C, W, M0) mit

S={s1, . . . , sk}, T ={t1, . . . ,tl},

F ={(si,tj)| (Si Tj) F =} {(ti,sj)| (Ti Sj) F=},

C(si) =Si, C(tj) =Tj,

(W(si,tj))(t) =

sSiW0(s, t) s und

(W(tj,si))(t) =

sSiW0(t, s) s fur alle tTj,

M0

(si) =sSi

M0

(s) s.

http://find/


16/24

Beispiel

Die Faltung von

s1

s2

t12t2

bzgl. {{t1, t2}}und {{s1, s2}} liefert das gefarbte S/T-System

s1s1 s2s

1 t

1fmit C(s1) ={s1, s2}, C(t

1) ={t1, t2},f(t1) = 2s1+1s2und f(t2) = 1s1+0s2.

http://find/


17/24

Von S/T-Systemen zu gefarbten S/T-Systemenund zuruck

Beobachtung 1

Sei STSein S/T-System und sei ctr(STS) eine Faltung von STS. Dannsind flt(ctr(STS)) und STS isomorph, d.h. bis auf Umbenennung derStellen und Transitionen gleich (ohne Beweis).



18/24

Von gefarbten S/T-Systemen zu S/T-Systemenund zuruck

Beobachtung 2

Sei GSTS= ({s1, . . . , sm}, {t1, . . . , tn}, F, C, W, M0} ein gefarbtesS/T-System und sei ctr(flt(GSTS) die Faltung von flt(GSTS) bzgl.{{s1} C(s1), . . . , {sm} C(sm)} und {{t1} C(t1), . . . , {tn} C(tn)}.Dann sind ctr(flt(GSTS)) und GSTS isomorph (ohne Beweis).



19/24

Schalten in gefarbten und entfaltetenS/T-Systemen (1)

Beobachtung 3

Sei GSTS= (S, T, F, C, W, M0) ein gefarbtes S/T-System undflt(GSTS) = (S, T, F, W, M0) dessen Entfaltung. Dann gilt:

M1[t, aM2 in GSTS

impliziert

M1[(t, a)M2 in flt(GSTS),

wobei Mi(s, x) = (Mi(s))(x) fur alle (s, x) S und i= 1, 2.



20/24

Schalten in gefarbten und entfaltetenS/T-Systemen (2)

Beweisskizze

Fur alle (s, x) (t, a) giltW((s, x), (t, a)) = ((W(s, t))(a))(x) (M1(s))(x) =M1(s, x).

Folglich ist (t, a) M1-aktiviert.

Sei M : S N, so dass M1[(t, a)M und sei (s, x) S.

Fall 1:(s, x) (t, a) (t, a). Dann giltM(s, x) =M1(s, x) W

((s, x), (t, a)) =

(M1(s))(x) ((W(s, t))(a))(x) = (M2(s))(x).

Alle weiteren Falle konnen in analoger Weise gezeigt werden.

http://find/


21/24

Schalten in S/T-Systemen und deren Faltungen (1)

Beobachtung 4

Sei STS= (S, T, F, W, M0) ein S/T-System. Sei

ctr(STS) = (S, T,F, C, W, M0)

die Faltung von STS bzgl. X ={S1, . . . , Sk} und Y ={T1, . . . , Tl}. SeitTj (fur ein j {1, . . . , l}). Dann gilt:

M1[tM2 in STS

impliziert

M1[tj, t M2 in ctr(GSTS),

wobei Mp(si) =

sSiMp(s) s fur i= 1, . . . , k und p= 1, 2.

http://find/


22/24

Schalten in S/T-Systemen und deren Faltungen(2)

Beweisskizze

Fur alle si tj gilt

(W(si,tj))(t) =

sSiW0(s, t) s

sSi

M1(s) s= M1(si).Folglich ist t

j (M

1, t)-aktiviert.

Sei M : S N, so dass M1[tj, tM und sei si S.

Fall 1: si tjtj

. Dann gilt M(si) = M1(si) (W(si,tj))(t) =

sSiM1(s)s

sSi

W0(s, t)s=

sSi(M1(s)sW0(s, t)s) =

sSi(M1(s) W0(s, t)) s=sSi M2(s) s.Alle weiteren Falle konnen in analoger Weise gezeigt werden.

http://find/


23/24

Folgerungen (1)

Folgerung 1Seien

GSTS= (S, T, F, C, W, M0) ein gefarbtes S/T-System,

t1, . . . , tn T und

aiC(ti) fur i= 1, . . . , n.Dann gilt:

M1[(t1, a1) (tn, an)M2 in GSTSgenau dann, wenn

M

1[(t1, a1) (tn, an)M

2 in flt(GSTS), wobeiMi(s, x) = (Mi(s))(x) fur i= 1, 2, alle sSund alle xC(s).

http://find/


24/24

Folgerungen (2)

Folgerung 2

Sei STS= (S, T, F, W, M0) ein S/T-System und sei ctr(STS) dieFaltung von STS bzgl. X ={S1, . . . , Sk} und Y ={T1, . . . , Tl}.Dann gilt:

M1[t1 tnM2 in STSgenau dann, wennM1[(f(t1), t1) (f(tn), tn) M2 in ctr(GSTS), wobeiMp(si) =iSi Mp(s) s und f(ti) =

tjgenau dann, wenn tiTj fur

i= 1, . . . , n und j= 1, . . . , l.


Documents

Gefaerbte Graphen auf Algorithmen