通信システムの計算

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

ミルナーによれば、「基本的なコンビネータの選択には、経済性を考慮して慎重に選ばれたとはいえ、決まった規範的な基準は何もない。我々の計算体系を特徴づけるのは、コンビネータの厳密な選択ではなく、解釈と数学的枠組みの選択である」。

言語表現は、ラベル付き遷移システムとして解釈される。これらのモデル間では、意味的等価性として双類似性が用いられる。

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

${\displaystyle P::=0\,\,\,|\,\,\,a.P_{1}\,\,\,|\,\,\,}$参照${\displaystyle A\,\,\,|\,\,\,P_{1}+P_{2}\,\,\,|\,\,\,P_{1}|P_{2}\,\,\,|\,\,\,P_{1}[b/a]\,\,\,|\,\,\,P_{1}{\バックスラッシュ }a\,\,\,}$

構文の構成要素は、上記の順序で次のとおりです。

非活性プロセス

不活性プロセス${\displaystyle 0}$有効なCCSプロセスです

アクション

そのプロセス${\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}$

• トニー・ホーアによって開発されたCommunicating sequential processes（CSP）は、CCSとほぼ同時期に登場した形式言語である。
• 通信プロセスの代数（ ACP）は、1982年にヤン・ベルグストラとヤン・ウィレム・クロップによって開発され、CCSと同様のクラスのプロセスについて推論するために、（普遍代数のスタイルで）公理的なアプローチを使用しています。
• 1980年代後半にロビン・ミルナー、ヨアヒム・パロウ、デビッド・ウォーカーによって開発されたπ計算は、プロセスが通信チャネルの名前を自ら伝達できるようにすることで、通信リンクのモビリティをCCSに拡張する。
• ジェーン・ヒルストンによって開発されたPEPAは、指数分布率と確率的選択の観点から活動のタイミングを導入し、パフォーマンス指標を評価することを可能にする。
• ヴィンセント・ダノス、ジャン・クリヴィーヌらが提唱した可逆通信並行システム（RCCS）は、CCSプロセスの実行に（部分的な）可逆性を導入する。

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

• 放送システムの計算
• 時間順序指定言語仕様（LOTOS）
• 空間的に明示的な生態モデルのためのプロセス計算（PALPS）は、確率的選択、場所、および場所の属性を備えたCCSの拡張です^{[ 2 ]。}
• Java Orchestration Language Interpreter Engine (Jolie) ^{[ 3 ]}

CCS類似システムの研究に用いられてきたモデル：

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

• ロビン・ミルナー：通信システムの計算、シュプリンガー・フェルラーク、ISBN 0-387-10235-31980年。
• ロビン・ミルナー著『通信と並行性』、プレンティス・ホール、国際コンピュータ科学シリーズ、ISBN 0-13-115007-31989年