Pi-Kalkül

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln 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

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

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

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

• Robin Milner: Communicating and Mobile Systems: the Pi-Calculus, Cambridge University Press, 1999, ISBN 0-521-65869-1
• Robin Milner: The Polyadic π-Calculus: A Tutorial, Logic and Algebra of Specification, 1993.
• Davide Sangiorgi und David Walker: The Pi-calculus: A Theory of Mobile Processes, Cambridge University Press, ISBN 0-521-78177-9

Weblinks

• PiCalculus
• Calculi for Mobile Processes
• FAQ on Pi-Calculus (PDF-Datei; 196 kB)