通信システムの計算

通信システム計算（CCS ）は、 1980年頃にロビン・ミルナーによって導入されたプロセス計算であり、その計算を解説した本のタイトルでもある。そのアクションは、正確に2人の参加者間の不可分な通信をモデル化する。形式言語には、並列合成、アクション間の加算、スコープ制限を記述するためのプリミティブが含まれる。CCSは、デッドロックやライブロックなどのシステムの特性の質的正しさを評価するのに役立つ。^[1]

ミルナーによれば、「基本的なコンビネータの選択は、経済性に十分配慮して選択されたとはいえ、標準的なものではありません。私たちの計算を特徴づけるのは、コンビネータの正確な選択ではなく、解釈と数学的枠組みの選択です。」

言語表現はラベル付けされた遷移システムとして解釈されます。これらのモデル間では、意味的同値性として 双類似性が使用されます。

アクション名のセットが与えられた場合、CCS プロセスのセットは次のBNF 文法によって定義されます。

${\displaystyle P::=0\,\,\,|\,\,\,a.P_{1}\,\,\,|\,\,\,A\,\,\,|\,\,\,P_{1}+P_{2}\,\,\,|\,\,\,P_{1}|P_{2}\,\,\,|\,\,\,P_{1}[b/a]\,\,\,|\,\,\,P_{1}{\backslash }a\,\,\,}$

構文の各部分は、上記の順序で

非アクティブなプロセス

非アクティブなプロセスは有効なCCSプロセスである${\displaystyle 0}$

アクション

プロセスはアクションを実行し、プロセスが継続する${\displaystyle a.P_{1}}$${\displaystyle a}$${\displaystyle P_{1}}$

プロセス識別子

識別子を使用してプロセスを参照するように記述します（識別子自体を含めることができます。つまり、再帰的な定義が許可されます）。${\displaystyle A{\overset {\underset {\mathrm {def} }{}}{=}}P_{1}}$${\displaystyle A}$${\displaystyle P_{1}}$${\displaystyle A}$

合計

プロセスは、プロセスとして、またはプロセスとして進行することができる。${\displaystyle P_{1}+P_{2}}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$

並列構成

${\displaystyle P_{1}|P_{2}}$プロセスと同時存在を伝える${\displaystyle P_{1}}$${\displaystyle P_{2}}$

名前の変更

${\displaystyle P_{1}[b/a]}$すべてのアクションの名前が次のように変更されたプロセスです。${\displaystyle P_{1}}$${\displaystyle a}$${\displaystyle b}$

制限

${\displaystyle P_{1}{\backslash }a}$行動のないプロセス${\displaystyle P_{1}}$${\displaystyle a}$

• Tony Hoareによって開発されたCommunicating Sequential Process (CSP) は、CCS と同時期に登場した形式言語です。
• 通信プロセス代数 (ACP) は、 1982年にJan BergstraとJan Willem Klopによって開発され、 CCS と同様のクラスのプロセスについて推論するために公理的なアプローチ (普遍代数のスタイル) を使用します。
• 80 年代後半にRobin Milner、Joachim Parrow、David Walkerによって開発された π 計算は、プロセスが通信チャネルの名前自体を通信できるようにすることで、通信リンクのモビリティによって CCS を拡張します。
• Jane Hillstonによって開発されたPEPA は、指数分布レートと確率的選択の観点からアクティビティのタイミングを導入し、パフォーマンス メトリックを評価できるようにします。
• Vincent Danos、Jean Krivine らによって導入された Reversible Communicating Concurrent Systems (RCCS) は、CCS プロセスの実行に (部分的な) 可逆性を導入します。

CCS をベースにした他の言語:

• 放送システムの微積分
• 時間順序仕様言語(LOTOS)
• 空間明示的生態学的モデルのためのプロセス計算（PALPS）は、確率的選択、場所、場所の属性を備えたCCSの拡張である^[2]
• Javaオーケストレーション言語インタプリタエンジン（Jolie）^[3]

CCS のようなシステムの研究で使用されてきたモデル:

• 歴史モノイド
• 俳優モデル

• ロビン・ミルナー：通信システムの計算、Springer Verlag、ISBN  0-387-10235-3。1980年。
• ロビン・ミルナー『コミュニケーションと並行性』、プレンティス・ホール、国際コンピュータサイエンスシリーズ、ISBN 0-13-115007-3、1989年