π計算

理論計算機科学において、π計算(またはパイ計算) はプロセス計算です。π計算では、チャネル名をチャネル自体に沿って通信できるため、計算中にネットワーク構成が変化する可能性のある同時計算を記述できます。

π計算は項が少なく、小さいながらも表現力豊かな言語です (§ 構文を参照)。関数型プログラムはπ計算にエンコードすることができ、エンコードは計算の対話的な性質を強調し、ゲームセマンティクスとの関連を描きます。spi計算や応用πなどのπ計算の拡張は、暗号プロトコルの推論に成功しています。並行システムの記述という本来の用途の他に、π計算はビジネスプロセス^[1]や分子生物学^[2]の推論にも使用されています。

π計算は、並行計算の特性を記述および分析するための数学的形式であるプロセス計算のファミリーに属します。実際、π計算は、λ 計算と同様に非常に最小限であるため、数値、ブール値、データ構造、変数、関数、または通常の制御フロー文 ( 、など) などのプリミティブさえも含まれていません。 if-then-elsewhile

π計算の中心となるのは名前の概念です。計算の単純さは、名前が通信チャネルと変数として二重の役割を果たすことにあります。

計算で利用可能なプロセス構成要素は以下のとおりです^[3]（正確な定義は次のセクションで説明します）。

• 同時実行性、と は同時に実行される 2 つのプロセスまたはスレッドです。${\displaystyle P\mid Q}$${\displaystyle P}$${\displaystyle Q}$
• コミュニケーション、どこで
  • 入力プレフィックス付けは 、 という名前の通信チャネルで送信されたメッセージを待機するプロセスであり、受信した名前を名前xにバインドします。通常、これは、ネットワークからの通信を期待するプロセス、または操作で一度だけ使用できるラベルのいずれかをモデル化します。${\displaystyle c\left(x\right).P}$${\displaystyle c}$${\displaystyle P}$cgoto c
  • 出力プレフィックスは、 として処理を進める前に名前がチャネルに出力されることを表します。通常、これはネットワーク上でのメッセージの送信または操作のいずれかをモデル化します。${\displaystyle {\overline {c}}\langle y\rangle .P}$${\displaystyle y}$${\displaystyle c}$${\displaystyle P}$goto c
• レプリケーションは で記述され、常に の新しいコピーを作成できるプロセスとして考えることができます。通常、これは、任意の数の操作を待機しているネットワーク サービスまたはラベルのいずれかをモデル化します。${\displaystyle !\,P}$${\displaystyle P}$cgoto c
• と書かれた新しい名前 の作成は、内に新しい定数x を割り当てるプロセスとして考えることができます。π計算の定数は名前のみで定義され、常に通信チャネルです。プロセス内での新しい名前の作成は、制限とも呼ばれます。${\displaystyle \left(\nu x\right)P}$${\displaystyle P}$
• nil プロセス ( ) は、実行が完了して停止したプロセスです。${\displaystyle 0}$

π計算のミニマリズムにより、通常の意味でのプログラムを書くことはできませんが、計算を拡張することは簡単です。特に、再帰、ループ、逐次合成などの制御構造と、一階関数、真理値、リスト、整数などのデータ型の両方を簡単に定義できます。さらに、分散や公開鍵暗号を考慮したπ計算の拡張が提案されています。Abadiと Fournet [1] による応用π計算は、任意のデータ型でπ計算を拡張することで、これらのさまざまな拡張を正式な基盤に置きました。

以下は、3 つの並列コンポーネントで構成されるプロセスの小さな例です。チャネル名x は、最初の 2 つのコンポーネントによってのみ認識されます。

${\displaystyle {\begin{aligned}(\nu x)&\;(\;{\overline {x}}\langle z\rangle .\;0\\&\;|\;x(y).\;{\overline {y}}\langle x\rangle .\;x(y).\;0\;)\\&\;|\;z(v).\;{\overline {v}}\langle v\rangle .0\end{aligned}}}$

最初の2つのコンポーネントはチャネルxで通信でき、名前y はzにバインドされます。したがって、プロセスの次のステップは次のようになります。

${\displaystyle {\begin{aligned}(\nu x)&\;(\;0\\&\;|\;{\overline {z}}\langle x\rangle .\;x(y).\;0\;)\\&\;|\;z(v).\;{\overline {v}}\langle v\rangle .\;0\end{aligned}}}$

残りのy は内部スコープで定義されているため影響を受けないことに注意してください。2番目と3番目の並列コンポーネントはチャネル名zで通信できるようになり、名前v はxにバインドされます。プロセスの次のステップは、

${\displaystyle {\begin{aligned}(\nu x)&\;(\;0\\&\;|\;x(y).\;0\\&\;|\;{\overline {x}}\langle x\rangle .\;0\;)\end{aligned}}}$

ローカル名xが出力されたので、 xのスコープが3番目のコンポーネントもカバーするように拡張されていることに注意してください。最後に、チャネルx を使用して名前x を送信できます。その後、同時に実行されているすべてのプロセスが停止します。

${\displaystyle {\begin{aligned}(\nu x)&\;(\;0\\&\;|\;0\\&\;|\;0\;)\end{aligned}}}$

Χを名前と呼ばれるオブジェクトの集合とする。π計算の抽象構文は、次のBNF文法から構築される（xとyはΧの任意の名前である）^{[4] 。}

${\displaystyle {\begin{aligned}P,Q::=&\;x(y).P\,\,\,\,\,&{\text{Receive on channel }}x{\text{, bind the result to }}y{\text{, then run }}P\\&\;|\;{\overline {x}}\langle y\rangle .P\,\,\,\,\,&{\text{Send the value }}y{\text{ over channel }}x{\text{, then run }}P\\&\;|\;P|Q\,\,\,\,\,\,\,\,\,&{\text{Run }}P{\text{ and }}Q{\text{ simultaneously}}\\&\;|\;(\nu x)P\,\,\,&{\text{Create a new channel }}x{\text{ and run }}P\\&\;|\;!P\,\,\,&{\text{Repeatedly spawn copies of }}P\\&\;|\;0&{\text{Terminate the process}}\end{aligned}}}$

以下の具体的な構文では、プレフィックスは並列合成 (|) よりも緊密に結合し、曖昧さを解消するために括弧が使用されます。

名前は、制約と入力プレフィックス構造によって束縛されます。正式には、π計算におけるプロセスの自由名の集合は、以下の表によって帰納的に定義されます。プロセスの束縛名集合は、自由名の集合に含まれないプロセスの名前として定義されます。

縮小意味論とラベル付き遷移意味論の両方の中心となるのは、構造的合同の概念です。2 つのプロセスは、構造まで同一である場合、構造的に合同です。特に、並列合成は可換かつ結合的です。

より正確には、構造的合同性は、プロセス構成要素によって保存され、次を満たす最小の同値関係として定義されます。

アルファ変換:

• ${\displaystyle P\equiv Q}$内の 1 つ以上のバインドされた名前を変更することによって、からを取得できます。${\displaystyle Q}$${\displaystyle P}$${\displaystyle P}$

並列合成の公理:

• ${\displaystyle P|Q\equiv Q|P}$
• ${\displaystyle (P|Q)|R\equiv P|(Q|R)}$
• ${\displaystyle P|0\equiv P}$

制限の公理:

• ${\displaystyle (\nu x)(\nu y)P\equiv (\nu y)(\nu x)P}$
• ${\displaystyle (\nu x)0\equiv 0}$

複製の公理:

• ${\displaystyle !P\equiv P|!P}$

制限と平行に関する公理:

• ${\displaystyle (\nu x)(P|Q)\equiv (\nu x)P|Q}$x がの自由名でない場合。${\displaystyle Q}$

この最後の公理は、「スコープ拡張」公理として知られています。この公理は、バインドされた名前x が出力アクションによって押し出され、xのスコープが拡張される方法を説明するため、重要です。 xが の自由名である場合、アルファ変換を使用して拡張を続行できます。 ${\displaystyle Q}$

が計算ステップを実行できる場合、と書き、その後は となります。この削減関係は、削減規則のセットの下で閉じられる最小の関係として定義されます。 ${\displaystyle P\rightarrow P'}$${\displaystyle P}$${\displaystyle P'}$ ${\displaystyle \rightarrow }$

プロセスがチャネルを介して通信する能力を捉える主な削減ルールは次のとおりです。

• ${\displaystyle {\overline {x}}\langle z\rangle .P|x(y).Q\rightarrow P|Q[z/y]}$

ここで、 は、 の自由な出現箇所を自由な名前に置き換えるプロセスを示します。の自由な出現箇所がが自由ではない場所に発生する場合、アルファ変換が必要になることがあります。${\displaystyle Q[z/y]}$${\displaystyle Q}$${\displaystyle z}$${\displaystyle y}$${\displaystyle y}$${\displaystyle z}$

追加のルールが 3 つあります。

• ならばまた。${\displaystyle P\rightarrow Q}$${\displaystyle P|R\rightarrow Q|R}$

この規則は、並列合成が計算を妨げないことを示しています。

• ならば、また。${\displaystyle P\rightarrow Q}$${\displaystyle (\nu x)P\rightarrow (\nu x)Q}$

このルールは、計算が制限の下で続行できることを保証します。

• かつかつならば、 でもあります。${\displaystyle P\equiv P'}$${\displaystyle P'\rightarrow Q'}$${\displaystyle Q'\equiv Q}$${\displaystyle P\rightarrow Q}$

後者の規則は、構造的に一致するプロセスは同じ削減を持つと述べています。

プロセスをもう一度考えてみましょう

${\displaystyle (\nu x)({\overline {x}}\langle z\rangle .0|x(y).{\overline {y}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0}$

還元意味論の定義を適用すると、還元が得られる。

${\displaystyle (\nu x)({\overline {x}}\langle z\rangle .0|x(y).{\overline {y}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0\rightarrow (\nu x)(0|{\overline {z}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0}$

簡約置換公理を適用すると、 の自由な出現がとしてラベル付けされることに注意してください。 ${\displaystyle y}$${\displaystyle z}$

次に、削減を行います

${\displaystyle (\nu x)(0|{\overline {z}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0\rightarrow (\nu x)(0|x(y).0|{\overline {x}}\langle x\rangle .0)}$

ローカル名xが出力されているため、 xのスコープが拡張され、3 番目のコンポーネントもカバーされることに注意してください。これは、スコープ拡張公理を使用してキャプチャされました。

次に、還元置換公理を用いると、

${\displaystyle (\nu x)(0|0|0)}$

最後に、並列合成と制限の公理を用いると、

${\displaystyle 0}$

あるいは、π計算にラベル付きの遷移セマンティクスを与えることもできます (通信システムの計算で行われたように)。このセマンティクスでは、アクション後の
ある状態から別の状態への遷移は次のように表記されます。 ${\displaystyle P}$${\displaystyle P'}$${\displaystyle \alpha }$

• ${\displaystyle P\,{\xrightarrow {\overset {}{\alpha }}}P'}$

ここで、状態とプロセスは入力アクション、出力アクション、またはサイレントアクションτのいずれかを表します。^[5]${\displaystyle P}$${\displaystyle P'}$${\displaystyle \alpha }$ ${\displaystyle a(x)}$ ${\displaystyle {\overline {a}}\langle x\rangle }$

ラベル付き意味論に関する標準的な結果は、構造的合同性までの還元意味論と一致するということであり 、これは ^[6]${\displaystyle P\rightarrow P'}$${\displaystyle P\,\xrightarrow {\overset {}{\tau }} \equiv P'}$

上記の構文は最小限のものですが、構文はさまざまな方法で変更できます。

非決定論的選択演算子を 構文に追加できます。 ${\displaystyle P+Q}$

名前の等価性 のテストを構文に追加できます。この一致演算子は、xと が同じ名前である場合にのみ として処理できます。同様に、名前の不等性に対する不一致演算子を追加することもできます。名前 (URL またはポインター) を渡すことができる実際のプログラムでは、このような機能がよく使用されます。計算内でこのような機能を直接モデル化するには、この機能と関連する拡張機能が役立つことがよくあります。 ${\displaystyle [x=y]P}$${\displaystyle P}$${\displaystyle y}$

非同期π計算^{[7] [8]では}、 継続のない出力、つまり という形式の出力アトムのみが許可され、計算が小さくなります。しかし、元の計算のどのプロセスも、受信プロセスからの明示的な確認応答をシミュレートするための追加チャネルを使用して、より小さな非同期π計算で表現できます。継続のない出力は転送中のメッセージをモデル化できるため、このフラグメントは、直感的には同期通信に基づく元のπ計算が、その構文内に表現力豊かな非同期通信モデルを持っていることを示しています。しかし、上で定義した非決定性選択演算子は、ガードなしの選択がガード付きの選択に変換されるため、この方法では表現できません。この事実は、非同期計算が（選択演算子を使用した）同期計算よりも表現力が厳密に劣ることを示すために使用されています。^[9]${\displaystyle {\overline {x}}\langle y\rangle }$

多項式π計算では、 1回のアクションで複数の名前を通信できます: (多項式出力)と(多項式入力)。この多項式拡張は、名前渡しプロセスの型を研究するときに特に役立ちますが、複数の引数が順番に渡されるプライベートチャネルの名前を渡すことによって、モナド計算でエンコードできます。エンコードは、次の節によって再帰的に定義されます。 ${\displaystyle {\overline {x}}\langle z_{1},...,z_{n}\rangle .P}$ ${\displaystyle x(z_{1},...,z_{n}).P}$

${\displaystyle {\overline {x}}\langle y_{1},\cdots ,y_{n}\rangle .P}$は次のようにエンコードされます${\displaystyle (\nu w){\overline {x}}\langle w\rangle .{\overline {w}}\langle y_{1}\rangle .\cdots .{\overline {w}}\langle y_{n}\rangle .[P]}$

${\displaystyle x(y_{1},\cdots ,y_{n}).P}$は次のようにエンコードされます${\displaystyle x(w).w(y_{1}).\cdots .w(y_{n}).[P]}$

その他のすべてのプロセス構造は、エンコードによって変更されません。

上記では、継続内のすべてのプレフィックスを同様にエンコードすることを示します。 ${\displaystyle [P]}$${\displaystyle P}$

複製の完全な能力は必要ありません。多くの場合、構造合同公理が である複製された入力のみを考慮します。 ${\displaystyle !P}$ ${\displaystyle !x(y).P}$${\displaystyle !x(y).P\equiv x(y).P|!x(y).P}$

などの複製された入力プロセスは、チャネルxがクライアントによって呼び出されるのを待機しているサーバーとして理解できます 。サーバーの呼び出しにより、プロセスの新しいコピーが生成されます。ここで、 a はサーバーの呼び出し中にクライアントからサーバーに渡される名前です。 ${\displaystyle !x(y).P}$${\displaystyle P[a/y]}$

高次のπ計算は、名前だけでなくプロセスもチャネルを介して送信されるように定義できます。高次のケースのキー削減規則は、

${\displaystyle {\overline {x}}\langle R\rangle .P|x(Y).Q\rightarrow P|Q[R/Y]}$

ここで、はプロセス項によってインスタンス化できるプロセス変数を表します。Sangiorgi は、プロセスを渡す機能によってπ計算の表現力は向上しないことを確立しました。プロセスPを渡すことは、代わりにPを指す名前を渡すだけでシミュレートできます。 ${\displaystyle Y}$

π計算は計算の普遍的なモデルです。これは、ミルナーが論文「プロセスとしての関数」^{[10]で初めて指摘したもので、} π計算におけるラムダ計算の 2 つのエンコードを示しています。1 つのエンコードは、積極的な (値呼び出し)評価戦略をシミュレートし、もう 1 つのエンコードは通常順序 (名前呼び出し) 戦略をシミュレートします。これら 2 つの場合において、重要な洞察は、環境バインディング (たとえば、「x は項にバインドされています」) を、項への接続を送り返すことでバインディングの要求に応答する複製エージェントとしてモデル化することです。 ${\textstyle M}$${\displaystyle M}$

これらのエンコードを可能にするπ計算の特徴は、名前渡しと複製（または、同等に、再帰的に定義されたエージェント）です。複製/再帰がない場合、π計算はチューリング完全ではなくなります。これは、再帰のない計算、さらには任意のプロセス内の並列コンポーネントの数が定数で制限される有限制御π計算でも、双模倣同値が決定可能になるという事実からわかります。^[11]

プロセス計算に関しては、π計算により双模倣同値の定義が可能になります。π 計算では、双模倣同値 (双類似性とも呼ばれる) の定義は、縮約意味論またはラベル付き遷移意味論のいずれかに基づきます。

π計算では、ラベル付き双模倣同値性を定義する方法が (少なくとも) 3 つあります。早期双類似性、後期双類似性、オープン双類似性です。これは、 π計算が値渡しプロセス計算であるという事実に由来しています。

このセクションの残りの部分では、と がプロセスを表し、 がプロセス上の二項関係を表すものとします。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle R}$

初期双相似性と後期双相似性は、ミルナー、パロー、ウォーカーのπ計算に関する最初の論文で定式化されました。^[12]

プロセス上の二項関係は、任意のプロセスのペアに対して、 ${\displaystyle R}$${\displaystyle (p,q)\in R}$

• そのとき、任意の名前に対して、かつとなる名前が存在する。${\displaystyle p\,{\xrightarrow {a(x)}}\,p'}$${\displaystyle y}$${\displaystyle q'}$${\displaystyle q\,{\xrightarrow {a(x)}}\,q'}$${\displaystyle (p'[y/x],q'[y/x])\in R}$
• 任意の非入力アクション に対して、かつとなるようなアクションが存在する場合、${\displaystyle \alpha }$${\displaystyle {p{\xrightarrow {\overset {}{\alpha }}}p'}}$${\displaystyle q'}$${\displaystyle q{\xrightarrow {\overset {}{\alpha }}}q'}$${\displaystyle (p',q')\in R}$
• およびとを入れ替えた対称的な要件。${\displaystyle p}$${\displaystyle q}$

プロセスと は早期双相似であると言われ、何らかの早期双模倣 のペアである場合に と書き込まれます。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle p\sim _{e}q}$${\displaystyle (p,q)\in R}$${\displaystyle R}$

後期双類似性では、遷移の一致は転送される名前とは独立していなければならない。プロセス上の二項関係は、すべてのプロセスペアに対して、 ${\displaystyle R}$${\displaystyle (p,q)\in R}$

• そのとき、ある者に対しては常に、またあらゆる名前 y に対しても、が成り立つ。${\displaystyle p{\xrightarrow {a(x)}}p'}$${\displaystyle q'}$${\displaystyle q{\xrightarrow {a(x)}}q'}$${\displaystyle (p'[y/x],q'[y/x])\in R}$
• 任意の非入力アクション に対して、 であれば、かつとなるようなものが存在することを意味します。${\displaystyle \alpha }$${\displaystyle p{\xrightarrow {\overset {}{\alpha }}}p'}$${\displaystyle q'}$${\displaystyle q{\xrightarrow {\overset {}{\alpha }}}q'}$${\displaystyle (p',q')\in R}$
• およびとを入れ替えた対称的な要件。${\displaystyle p}$${\displaystyle q}$

プロセスと は、何らかの後期双模倣 のペアである場合に、後期双類似 であると記述されます。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle p\sim _{l}q}$${\displaystyle (p,q)\in R}$${\displaystyle R}$

と は両方とも、すべてのプロセス構成によって保存されないという意味で合同関係ではないという問題を抱えています。より正確には、 であるが であるようなプロセスと が存在します。この問題は、それぞれ早期合同と後期合同として知られる、およびに含まれる最大合同関係を考慮することで解決できます。 ${\displaystyle \sim _{e}}$${\displaystyle \sim _{l}}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p\sim _{e}q}$${\displaystyle a(x).p\not \sim _{e}a(x).q}$${\displaystyle \sim _{e}}$${\displaystyle \sim _{l}}$

幸いなことに、この問題を回避する第3の定義、すなわちサンジョルジによる開放双相似性の定義が可能です。 ^[13]

過程上の二項関係は、すべての要素のペアおよびすべての名前置換およびすべてのアクションに対して、かつとなるものが存在するとき、開双模倣です。 ${\displaystyle R}$${\displaystyle (p,q)\in R}$${\displaystyle \sigma }$${\displaystyle \alpha }$${\displaystyle p\sigma {\xrightarrow {\overset {}{\alpha }}}p'}$${\displaystyle q'}$${\displaystyle q\sigma {\xrightarrow {\overset {}{\alpha }}}q'}$${\displaystyle (p',q')\in R}$

プロセスと は、何らかの開いた双模倣 のペアの場合、 と書き表される、開いた双類似であると言われています。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle p\sim _{o}q}$${\displaystyle (p,q)\in R}$${\displaystyle R}$

早期、後期、およびオープンな双相似性は異なります。包含関係は適切であるため、。 ${\displaystyle \sim _{o}\subsetneq \sim _{l}\subsetneq \sim _{e}}$

非同期π計算などの特定のサブ計算では、後期双相似性、早期双相似性、および開放双相似性が一致することが知られています。ただし、この設定では、非同期双相似性という概念の方が適切です。文献では、開放双相似性という用語は通常、プロセスと関係が区別関係によってインデックス付けされる、より洗練された概念を指します。詳細は、上記のサンジョルジの論文に記載されています。

あるいは、リダクション セマンティクスから直接双模倣同値性を定義することもできます。プロセスがname での入力または出力を直ちに許可する場合、と記述します。 ${\displaystyle p\Downarrow a}$${\displaystyle p}$${\displaystyle a}$

過程上の二項関係は、対称関係であり、すべての要素のペアに対して次の式を満たす場合、有刺双模倣である。 ${\displaystyle R}$${\displaystyle (p,q)\in R}$

（１）すべての名前に対して${\displaystyle p\Downarrow a}$${\displaystyle q\Downarrow a}$${\displaystyle a}$

そして

（２）あらゆる還元には還元が存在する${\displaystyle p\rightarrow p'}$${\displaystyle q\rightarrow q'}$

となる。 ${\displaystyle (p',q')\in R}$

となる有刺双類似が存在するとき、と は有刺双類似であるといいます。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle R}$${\displaystyle (p,q)\in R}$

コンテキストを穴 [] を持つπ項として定義すると、2 つのプロセス P と Q は、すべてのコンテキストに対して、およびが有刺双相似である場合に、有刺合同、と書き表されると言います。有刺合同は、初期双相似性によって誘導される合同と一致することがわかります。 ${\displaystyle P\sim _{b}Q\,\!}$${\displaystyle C[]}$${\displaystyle C[P]}$${\displaystyle C[Q]}$

π計算は、さまざまな種類の並行システムを説明するために使用されてきました。実際、最近のアプリケーションのいくつかは、従来のコンピュータ サイエンスの領域外にあります。

1997 年、Martin Abadiと Andrew Gordon は、暗号プロトコルの記述と推論のための形式表記法として、π計算の拡張である Spi 計算を提案しました。Spi 計算は、暗号化と復号化のプリミティブを追加してπ計算を拡張します。2001 年、Martin Abadiと Cedric Fournet は、暗号プロトコルの処理を一般化して、応用π計算を生み出しました。現在では、応用π計算のさまざまなバリエーションに関する研究が盛んに行われており、実験的な検証ツールも数多くあります。1 つの例は、Bruno Blanchet によるツールProVerif [2] で、応用π計算を Blanchet の論理プログラミング フレームワークに翻訳したものです。もう1つの例は、Andrew GordonとAlan JeffreyによるCryptyc [3]です。これは、暗号プロトコルの認証プロパティをチェックできる型システムの基礎として、WooとLamの対応アサーション法を使用しています。

2002年頃、ハワード・スミスとピーター・フィンガーは、π計算がビジネスプロセスをモデリングするための記述ツールになるのではないかと興味を持ちました。2006年7月までに、コミュニティではこれがどれほど有用であるかについての議論が行われました。最近では、π計算はビジネスプロセスモデリング言語（BPML）とマイクロソフトのXLANGの理論的基礎を形成しました。 ^[14]

π計算は分子生物学でも関心を集めています。1999 年、アビブ レゲフとエフード シャピロは、細胞シグナル伝達経路 (いわゆるRTK / MAPKカスケード)、特にこれらのコミュニケーション タスクを実行する分子「レゴ」を π 計算の拡張で記述できることを示しました。^[2]この独創的な論文に続いて、他の著者は最小限の細胞の代謝ネットワーク全体を記述しました。[ ^15] 2009 年、アンソニー ナッシュとサラ カルヴァラは、Dictyostelium discoideum の凝集を指示するシグナル伝達をモデル化するπ計算フレームワークを提案しました。 ^[16]

π計算はもともと、ウッフェ・エングバーグとモーゲンス・ニールセンのアイデアに基づいて、ロビン・ミルナー、ヨアヒム・パロー、デイビッド・ウォーカーによって1992年に開発されました。[ 17 ^{]これは、ミルナーのプロセス計算CCS（}通信システムの計算）の研究の延長と見ることができます。チューリング講演で、ミルナーはπ計算の開発を、アクターにおける価値とプロセスの均一性を捉える試みとして説明しています。^[18]

次のプログラミング言語は、π計算またはその変形の 1 つを実装しています。

• ビジネスプロセスモデリング言語(BPML)
• オッカムπ
• ピクト
• JoCaml ( Join計算に基づく)
• ローラン

• ミルナー、ロビン(1999)。通信とモバイルシステム: π計算。ケンブリッジ、イギリス: ケンブリッジ大学出版局。ISBN 0-521-65869-1。
• ミルナー、ロビン(1993)。「ポリアディック π 計算: チュートリアル」。FL ハマー、W. ブラウアー、H. シュウィッテンベルク (編)。仕様の論理と代数。Springer-Verlag。
• Sangiorgi, Davide ; Walker, David (2001). π計算: モバイルプロセスの理論. ケンブリッジ、イギリス: Cambridge University Press. ISBN 0-521-78177-9。