Embed Size (px)
DESCRIPTION
Milners Kalkül Kommunizierender Systeme (CCS). Arnaud Fietzke betreut durch Tim Priesnitz, Guido Tack. Proseminar: Theorie kommunizierender Systeme. Programming Systems Lab – Prof. Gert Smolka. A = a.A ‘ B = b.B ‘ A ‘ = b.A B ‘ = c.B. Modellierung nebenläufiger Systeme. a. _. >. - PowerPoint PPT Presentation
Citation preview
Milners Kalkül Kommunizierender Systeme(CCS)
Arnaud Fietzkebetreut durch Tim Priesnitz, Guido Tack
Programming Systems Lab – Prof. Gert Smolka
Proseminar: Theorie kommunizierender Systeme
Modellierung nebenläufiger Systeme
A A‘
a
B‘ Bc_
_b
>
b
A = a.A‘ B = b.B‘A‘ = b.A B‘ = c.B
<
_ _
Modellierung nebenläufiger Systeme
A A‘
a
B‘ Bc_b
_b
>
<
A = a.A‘ B = b.B‘A‘ = b.A B‘ = c.BA = a.A‘ B = b.B‘A‘ = b.A B‘ = c.B
A|B mit
_ _
CCS
Übersicht
• Einführung
• Syntax CCS
• Semantik CCS• Idee• Strukturelle Kongruenz• Reaktion
Einführung
Prozessalgebra:
• algebraische Modellierung von nebenläufigen Prozessen
• Darstellung komplexer Systeme mit Hilfe weniger Operatoren
• ermöglicht automatische Verifikation
Prozessalgebren: Ansätze
• CCS (Calculus of Communicating Systems)[Milner '80]
• CSP (Communicating Sequential Processes)[Hoare '85]
• ACP (Algebra of Communicating Processes)[Bergstra & Klop '84]
• LOTOS (Language of Temporal Ordered Specification)[Brinksma & Draft '88]
Syntax CCS
Definition:
P ::= A<a1,...,an>Menge P der Prozessausdrücke:
mit I endliche IndexmengeiI
| i.Pi
0 := mit I = 0iI
i.Pi
N N { }N = {a,b,c,…} Namen
_
| P1|P2 | new a P
System von nebenläufigen Prozessen:
P1 | … | Pn mit P1 ...=
Pn ...=
...
Semantik CCS
Idee: "chemical machine"
An “Ports“ können beobachtbare Aktionenstattfinden ( N N)
_
[Berry & Boudol '89]
Semantik CCS
Idee: "chemical machine"
Komplementäre “Ports“ sind Reaktionspunktez.B. und
_
[Berry & Boudol '89]
Semantik CCS
Idee: "chemical machine"
"Moleküle" können sichannähern und reagierenannähern
[Berry & Boudol '89]
Prozess-Kongruenz
Definition :
Äquivalenzrelation (reflexiv, symmetrisch, transitiv) über P mit
.P + Mnew a PP|RR|P
.Q + Mnew a QQ|RR|Q
falls P Q
Prozess-Kontext
Definition :
C ::= | a.C+M | new a C | C|P | P|C
C[Q] : Substitution von [] in C durch QFür C=[] gilt: C[Q] = Q
[]
Eine bestimmte Prozess-Kongruenz lässt sich durchein Gleichungssystem definieren :
3
Prozess-Kongruenz
Eine bestimmte Prozess-Kongruenz lässt sich durchein Gleichungssystem definieren :
3
• erfüllt alle Gleichungen aus• für jede Sequenz Q1,…Qn (n≥1) von Ausdrücken gilt Q1 Qn falls Qi = C[P] und Qi+1 = C[P‘] und es gilt: P P‘ oder P‘ P
3
Strukturelle Kongruenz
Definition:
(1) Änderung gebundener Namen
Prozess-Kongruenz , definiert durch Gleichungen:
(new b) a.b (new c) a.cBeispiel:
Strukturelle Kongruenz
Definition:
(1) Änderung gebundener Namen
(2) Umordnung der Terme in Summen
Prozess-Kongruenz , definiert durch Gleichungen:
a.0 + b.0 b.0 + a.0Beispiel:
Strukturelle Kongruenz
Definition:
(1) Änderung gebundener Namen
(2) Umordnung der Terme in Summen(3) P|0 P
Prozess-Kongruenz , definiert durch Gleichungen:
, P|Q Q|P, P|(Q|R) (P|Q)|R
Strukturelle Kongruenz
Definition:
(1) Änderung gebundener Namen
(2) Umordnung der Terme in Summen(3) P|0 P, P|Q Q|P, P|(Q|R) (P|Q)|R
(4) new a (P|Q) P|new a Q falls a nicht frei in P
Prozess-Kongruenz , definiert durch Gleichungen:
, new ab P new ba Pnew a 0 0,
Strukturelle Kongruenz
Definition:
(1) Änderung gebundener Namen
(2) Umordnung der Terme in Summen(3) P|0 P, P|Q Q|P, P|(Q|R) (P|Q)|R
(5) A<b> { } PA falls A(a) = PA
Prozess-Kongruenz , definiert durch Gleichungen:
ba
(4) new a (P|Q) P|new a Q falls a nicht frei in P , new ab P new ba Pnew a 0 0
,
Strukturelle Kongruenz
Definition:
(1) Änderung gebundener Namen
(2) Umordnung der Terme in Summen(3) P|0 P, P|Q Q|P, P|(Q|R) (P|Q)|R
(5) A<b> { } PA falls A(a) = PA
Prozess-Kongruenz , definiert durch Gleichungen:
ba
(4) new a (P|Q) P|new a Q falls a nicht frei in P , new ab P new ba Pnew a 0 0
,Notation:a Sequenz von Namen a1,…,an
Standardform
Definition:
Ausdrucknew a (M1|…|Mn) mit Mi nichtleere Summe (1 ≤ i ≤ n)
ist in Standardform.
Falls n=0, M1|…|Mn = 0Falls a leer, fällt new a weg
Theorem:
Jeder Prozessausdruck ist strukturell kongruent zu einerStandardform.
Semantik nebenläufiger Prozessausdrücke
Idee: "chemical machine"
"Moleküle" können sichannähern und reagierenreagieren
[Berry & Boudol '89]
Semantik nebenläufiger Prozessausdrücke
Idee: "chemical machine"
"Moleküle" können sichannähern und reagieren
[Berry & Boudol '89]
Semantik nebenläufiger Prozessausdrücke
Idee: "chemical machine"
"Moleküle" können sichannähern und reagieren
Reaktionen sind von aussennicht mehr beobachtbar:-Transitionen
[Berry & Boudol '89]
Reaktion
Definition:Relation auf P wird durch Regeln definiert:
TAU : .P + M P
PAR : P P'P|Q P'|Q
RES : P P'new a P new a
P'STRUCT : P P'
Q Q'falls P Q und P' Q'
REACT : (a.P + M)|(a.Q + N) P|Q
Beispiel
A = a.A‘ B = b.B‘
A‘ = b.A B‘ = c.B_ _
A‘|B mit
Inferenzbaum:
A‘|B A|B‘
b.A|b.B‘ A|B‘_
STRUCT
REACT
Beispiel
Alternative Reaktionen:
P = a.0 | a.A | a.B_ _
Zwei Reaktionen sind möglich:
P A|a.B_
Beispiel
Alternative Reaktionen:
P = a.0 | a.A | a.B_ _
P A|a.BP a.A| Bund
Zwei Reaktionen sind möglich:
Indeterminismus durch Reaktion
__
Referenzen
• Milner, R., Communicating and Mobile Systems: the π – Calculus, Cambridge University Press, 1999
• Milner, Operational & Algebraic Semantics of Concurrent Processes Handbook of Theoretical Computer Science B, Elsevier, 1990
