プロセス計算（プロセスけいさん、）またはプロセス代数（プロセスだいすう、）は、計算機科学において並行システムを形式的にモデリングする各種手法の総称。プロセス計算は、独立エージェントやプロセスの集まりにおける相互作用/通信/同期を抽象的に記述するツールである。また、プロセス記述を操作・分析可能にする代数学的規則も提供し、プロセス間の等価性について（双模倣性を使った）形式的推論を可能とする。主な具体例としては、CSP、CCS、ACP がある。近年ではこれら以外に π計算()、アンビエント計算、PEPA などもある。プロセス計算には非常に様々な手法が存在するが（分子の相互作用の研究に特化し、確率論的振る舞いやタイミング情報を扱うものもある）、全てのプロセス計算に共通する機能もいくつか存在する。プロセス計算を定義するには、通信手段を提供することを目的とした「名前（name）」または「通信路（channel）」を始点とする。多くの実装で、通信路内には効率向上のための複雑な構造があるが、理論モデルではそれらは抽象化によって消え去る。名前に加えて、古いプロセスから新たなプロセスを形成する手段が必要である。そして、以下のような演算子が一般に存在する。2つのプロセス formula_1 と formula_2 の並列合成は formula_3 のように記述され、逐次型計算モデルとプロセス計算の重要な違いとなっている。並列合成は formula_1 と formula_2 における計算を同時並行的かつ独立に進めることを可能にする。しかし同時に相互作用も可能で、同期や formula_1 から formula_2（あるいは逆）への通信路による情報の受け渡しが可能である。エージェントやプロセスは1度に複数の通信路と接続可能である。通信路は同期型と非同期型がある。同期通信路の場合、メッセージを送ったエージェントは相手がそのメッセージを受け取るのを待つ。非同期通信路ではそのような同期は不要である。一部のプロセス計算（特にπ計算）では、通信路そのものをメッセージとして（他の）通信路経由で送信することができ、プロセス間の連結トポロジーを変更できる。また一部のプロセス計算では、計算途中に通信路を生成することができる。相互作用は情報の流れる方向が決まっている場合が多い。すなわち、入力と出力は双対的相互作用プリミティブとして区別される。プロセス計算では一般に入力演算子（例えば formula_8）と出力演算子（例えば formula_9）を定義して、それらを区別する。これらには相互作用点として名前がつけられ（ここでは formula_10）、双対的相互作用プリミティブとして同期に使われる。情報を交換するには、出力プロセスから入力プロセスに情報が流れるということになる。出力プリミティブには送信すべきデータを指定する。formula_9 の場合、formula_12 がそのデータである。同様に入力はデータを受信することを期待し、1つ以上の束縛変数を受信データと置換するためのプレースホルダーとして用いる。formula_8 の場合、formula_14 がそれである。一回の相互作用で交換できるデータの種類の選択は、個々のプロセス計算の大きな特徴の1つである。場合によっては、相互作用を時間的に順番に行いたいことがある。例えば、「まず formula_10 でデータを受信し、そのデータを formula_12 に送信する」というようなアルゴリズム記述はよくある。逐次合成（Sequential composition）はそのようなプロセスで使われる。これは他の計算モデルでもよく使われる。プロセス計算では逐次化演算子は一般に入力や出力と結びついていることが多い。例えば、プロセス formula_17 は、入力を formula_10 で待ち受ける。そして入力があったときだけプロセス formula_1 を起動し、その際に受信データは formula_10 によって識別子 formula_14 と置換されている。プロセス計算の計算の本質を含む操作的リダクション規則は、並列合成、逐次化、入力、出力のみで与えられる。リダクションの詳細は個々のプロセス計算で異なるが、本質はほぼ同じである。リダクション規則は次の通りである。このリダクション規則は次のように解釈される。出力操作の継続としてformula_1 ができる範囲は、プロセス計算の特徴に大きく影響する。プロセスが、ある相互作用点との間に形成できるコネクションの数は制限されない。しかし、相互作用点における干渉は発生しうる。コンパクトで最小なシステムを合成する際、干渉を抑えることは重要である。隠蔽（Hiding）操作はエージェントの合成と並行して、相互作用点間のコネクションの制御を可能にする。隠蔽の表し方は様々である。例えばπ計算では、formula_1 における名前 formula_10 の隠蔽は formula_39 と表され、CSP では formula_40 のように表される。ここまで説明した操作は有限の相互作用だけであり、停止しない場合も含む完全な計算を表すには不十分である。再帰（Recursion）操作と複製（Replication）操作は、有限の記述で無限の振る舞いを表せる。再帰は逐次モデルでもよく使われる。複製 formula_41 は、可算無限個のプロセス formula_1 の並列合成を表すと理解できる。プロセス計算には一般に相互作用点を持たない Null プロセスも含まれる（formula_44、formula_45、formula_46、formula_47 など様々な表記法がある）。Null プロセスは何もせず、再帰的なプロセス生成の始点（または終点）として使われる。20世紀前半、非形式的な概念だった「計算可能関数」を表現する形式手法として、μ再帰関数、チューリングマシン、ラムダ計算などが提案された。これらは相互に変換可能であり、等価であることから、チャーチ＝チューリングのテーゼが提唱された。もう1つの特徴はあまり言及されない。これらはいずれも「逐次的」計算のモデルだったのである。計算機科学の次の段階の発展において、並行性と通信を明確に表現できる計算の記法の確立が必要とされた。そのような状況で生まれたのが、プロセス計算、ペトリネット、アクターモデルなどの並行性モデルである。プロセス計算の研究は、ロビン・ミルナーが1973年から1980年にかけて行った Calculus of Communicating Systems (CCS) の研究が最初であった。アントニー・ホーアの Communicating Sequential Processes (CSP) は1978年に発表され、そこから1980年代初めにかけて完全なプロセス計算の研究が行われた。CCS と CSP をさらに発展させようという研究も行われた。1982年、Jan Bergstra と Jan Willem Klop は後に Algebra of Communicating Processes (ACP) と呼ばれるものの研究を開始し、「プロセス代数（Process algebra）」という用語を生み出した。CCS と CSP と ACP がプロセス計算のファミリーを形成し、その後の様々なプロセス計算の源流となっている。プロセス計算は非常に様々なものがあり、ここで解説したパラダイムに適合しないものもある。特筆すべき例としてアンビエント計算がある。現在、プロセス計算の研究では以下の問題が中心課題となっている。 は、相互に通信するプロセスの履歴を表現できる汎用的な である。その場合、プロセス計算は一定の方式で history monoid 上に課された形式言語である。すなわち、history monoid は同期を含めたイベントの並びだけを記録するが、その際の状態遷移は記録しない。従って、history monoid にとってのプロセス計算は、 にとっての形式言語と同じである（形式言語は、クリーネ閉包で生成可能なアルファベットの有限長文字列の集合の部分集合である）。ペトリネットやアクターモデルといった他の並行計算モデルとの違いは、通信路を使った通信を行う点である。通信路を含めたのは、それによってある種の代数学的手法が可能になるためであり、それによってプロセスを代数学的に理解しやすくなっている。

出典:wikipedia