プロセス計算

2つのプロセスの並列合成${\displaystyle {\mathit {P}}}$そして${\displaystyle {\mathit {Q}}}$通常は、${\displaystyle P\vert Q}$は、プロセス計算を逐次計算モデルから区別する重要な基本要素です。並列合成により、${\displaystyle {\mathit {P}}}$そして${\displaystyle {\mathit {Q}}}$同時に独立して進行する。しかし、相互作用、つまり同期と情報の流れも可能になる。${\displaystyle {\mathit {P}}}$に${\displaystyle {\mathit {Q}}}$（またはその逆）両者が共有するチャネル上で通信が行われます。重要なのは、1つのプロセスが同時に複数のチャネルに接続できる場合があることです。

チャネルは同期型と非同期型があります。同期型チャネルの場合、メッセージを送信するプロセスは、別のプロセスがメッセージを受信するまで待機します。非同期型チャネルは、このような同期を必要としません。一部のプロセス計算（特にπ計算）では、チャネル自体を（他の）チャネルを介してメッセージとして送信することができ、プロセス間の接続トポロジーを変更できます。また、一部のプロセス計算では、計算の実行中にチャネルを作成することもできます。

相互作用は、（常にではないが）方向性のある情報の流れになり得る。つまり、入力と出力は、双対的な相互作用プリミティブとして区別できる。このような区別を行うプロセス計算は、通常、入力演算子（例：${\displaystyle x(v)}$）と出力演算子（例：${\displaystyle x\langle y\rangle }$) どちらも相互作用点 (ここでは${\displaystyle {\mathit {x}}}$) は、デュアルインタラクションプリミティブと同期するために使用されます。

情報が交換される場合、それは出力プロセスから入力プロセスへと流れます。出力プリミティブは、送信されるデータを指定します。${\displaystyle x\langle y\rangle }$このデータは${\displaystyle y}$同様に、入力がデータを受け取ることを想定している場合、1 つ以上のバインド変数が、データが到着したときに置き換えられるプレースホルダーとして機能します。${\displaystyle x(v)}$、${\displaystyle v}$がその役割を担う。相互作用において交換可能なデータの種類を選択することは、異なるプロセス計算を区別する重要な特徴の一つである。

相互作用は時間的に順序付けられる必要がある場合がある。たとえば、次のようなアルゴリズムを指定することが望ましい場合がある。まず、あるデータを受信する。${\displaystyle {\mathit {x}}}$そしてそのデータを送信する${\displaystyle {\mathit {y}}}$逐次合成はこのような目的に使用できます。 これは他の計算モデルでよく知られています。プロセス計算では、逐次化演算子は通常、入力または出力、あるいはその両方と統合されます。たとえば、プロセス${\displaystyle x(v)\cdot P}$入力を待ちます${\displaystyle {\mathit {x}}}$この入力が発生したときにのみ、プロセスが開始されます。${\displaystyle {\mathit {P}}}$受信したデータによってアクティブ化されます${\displaystyle {\mathit {x}}}$識別子の代わりに${\displaystyle {\mathit {v}}}$。

プロセス計算の計算の本質を包含する主要な演算削減規則は、並列合成、逐次化、入力、出力という観点のみで表すことができる。この削減の詳細は計算の種類によって異なるが、本質はおおむね同じである。削減規則は以下のとおりである。

${\displaystyle x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]}$

この還元規則の解釈は次のとおりです。

1. そのプロセス${\displaystyle x\langle y\rangle \cdot P}$メッセージを送信します。${\displaystyle {\mathit {y}}}$水路に沿って${\displaystyle {\mathit {x}}}$二重に、そのプロセスは${\displaystyle x(v)\cdot Q}$チャネルでそのメッセージを受信する${\displaystyle {\mathit {x}}}$。
2. メッセージが送信されると、${\displaystyle x\langle y\rangle \cdot P}$プロセスになる${\displaystyle {\mathit {P}}}$、 その間${\displaystyle x(v)\cdot Q}$プロセスになる${\displaystyle Q[^{y}\!/\!_{v}]}$それは${\displaystyle {\mathit {Q}}}$プレースホルダー付き${\displaystyle {\mathit {v}}}$に置き換えられた${\displaystyle {\mathit {y}}}$受信したデータは${\displaystyle {\mathit {x}}}$。

プロセスのクラス${\displaystyle {\mathit {P}}}$出力演算の継続が計算の性質に大きく影響するため、範囲が広がることが許容されます。

プロセスは、特定の相互作用点で形成できる接続の数を制限しません。しかし、相互作用点では干渉（つまり相互作用）が許容されます。コンパクトで最小限の構成的システムを合成するには、干渉を制限する能力が不可欠です。隠蔽操作により、プロセスを並列に構成する際に、相互作用点間の接続を制御できます。隠蔽はさまざまな方法で表現できます。たとえば、π計算では、名前の隠蔽が${\displaystyle {\mathit {x}}}$で${\displaystyle {\mathit {P}}}$次のように表現できます${\displaystyle (\nu \;x)P}$一方、CSPでは次のように書かれるかもしれない。${\displaystyle P\setminus \{x\}}$。

これまで説明してきた操作は有限の相互作用しか記述しておらず、したがって、非終了的な振る舞いを含む完全な計算可能性には不十分である。再帰と複製は、無限の振る舞いを有限に記述することを可能にする操作である。再帰は逐次処理の世界ではよく知られている。複製${\displaystyle !P}$は、可算無限個の並列合成を省略したものと理解できる。${\displaystyle {\mathit {P}}}$プロセス:

${\displaystyle !P=P\mid !P}$

プロセス計算には一般的にヌルプロセス（さまざまな表記法で次のように表される）も含まれます。${\displaystyle {\mathit {nil}}}$、${\displaystyle 0}$、${\displaystyle {\mathit {STOP}}}$、${\displaystyle \delta }$（または他の適切な記号）は、相互作用点を持たない。これは完全に不活性であり、その唯一の目的は、より興味深いプロセスを生成するための誘導アンカーとして機能することである。