Pi-Kalkül

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
QS-Informatik

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)
Begründung: Ist für mich immer noch unverständlich --Eorhim 12:03, 5. Mai 2010 (CEST)

π-Kalkül ist ein Prozesskalkül, der von Robin Milner, Joachim Parrow und David Walker als Nachfolger des Calculus of Communicating Systems (CCS) entwickelt wurde. Ziel war die Entwicklung einer formellen Beschreibung von nebenläufigen Systemen, die sich während der Laufzeit verändern.

Ein Anwendungszweck dieser Art von Verfahren ist die Simulation von Nebenläufigkeiten wie zum Beispiel Threads oder Prozessen auf modernen Mehrkernprozessoren, da bei der Programmierung von Software, welche diese Funktionalität ausnützt, komplexe Randbedingungen ins Spiel kommen, die mittels einer solchen Simulation leichter in den Griff zu bekommen sind.

Konstrukte[Bearbeiten]

Name Syntax
Nebenläufigkeit P \mid Q
Eingabepräfix c\left(x\right).P
Ausgabepräfix \overline{c} \langle y \rangle.P
Replikation !\,P
Neu \left(\nu x\right)P
Null-Prozess 0

Formale Definition[Bearbeiten]

Seien X eine Menge von Namen und x und y Elemente dieser Menge. Die folgende Grammatik in Backus-Naur-Form beschreibt dann die Sprache des π-Kalküls:


\begin{align}

P ::= \, & x(y).P \,\,\, \\
|\,\,\, & \overline{x} \langle y \rangle.P \,\,\, \\
|\,\,\, & P|P \,\,\, \\
|\,\,\, & (\nu x)P  \,\,\, \\
|\,\,\, & !P \,\,\, \\
|\,\,\, & 0 

\end{align}

Beispiel[Bearbeiten]

Drei nebenläufige Prozesse.


\begin{align}

     &  \begin{align}
                (\nu x) \; & ( \; \overline{x} \langle z \rangle . \; 0 \\  
                           & | \; x(y). \; \overline{y}\langle x \rangle . \; x(y). \; 0 \; ) 
        \end{align} \\


| \; & z(v) . \; \overline{v}\langle v \rangle . 0 

\end{align}

Literatur[Bearbeiten]

Weblinks[Bearbeiten]