通信プロセスの代数

ACP は瞬間的で原子的なアクションを使用します(${\displaystyle {\mathit {a,b,c,...}}}$）をその基本要素として使用します。一部のアクションには特別な意味があります。例えば、アクション${\displaystyle \delta }$これは行き詰まりや停滞を表し、アクション$\displaystyle \tau }$これは、沈黙した動作（特定のアイデンティティを持たない抽象化された動作）を表します。

さまざまな演算子を使用して、アクションを組み合わせてプロセスを形成できます。これらの演算子は、大まかに言って、基本的なプロセス代数、並行処理、および通信を提供するものとして分類できます。

• 選択と順序付け– 代数演算子の中で最も基本的なものは、代替演算子 (${\displaystyle +}$) アクションの選択肢とシーケンス演算子(${\displaystyle \cdot }$）は、アクションの順序を指定します。たとえば、プロセス

${\displaystyle (a+b)\cdot c}$

まず、どちらかを実行することを選択します。${\displaystyle {\mathit {a}}}$または${\displaystyle {\mathit {b}}}$そして、アクションを実行する${\displaystyle {\mathit {c}}}$選択方法${\displaystyle {\mathit {a}}}$そして${\displaystyle {\mathit {b}}}$作成方法は重要ではなく、指定されていません。交替合成は可換ですが、逐次合成は可換ではありません（時間が順方向に流れるため）。

• 並行処理– 並行処理を記述できるようにするために、ACP はマージ演算子と左マージ演算子を提供します。マージ演算子は、${\displaystyle \vert \vert }$は、個々の動作が交互に行われる 2 つのプロセスの並列合成を表します。左マージ演算子は、${\displaystyle \vert \lfloor }$は、マージと同様の意味を持つ補助演算子ですが、常に左側のプロセスから最初のステップを選択するという制約があります。例として、プロセス

${\displaystyle (a\cdot b)\vert \vert (c\cdot d)}$

アクションを実行する${\displaystyle a,b,c,d}$いずれのシーケンスにおいても${\displaystyle abcd,acbd,acdb,cabd,cadb,cdab}$一方、そのプロセスは

${\displaystyle (a\cdot b)\vert \lfloor (c\cdot d)}$

シーケンスのみ実行可能${\displaystyle abcd,acbd,acdb}$左マージ演算子はアクションが${\displaystyle {\mathit {a}}}$最初に発生する。

• 通信—プロセス間の相互作用（または通信）は、バイナリ通信演算子を使用して表されます。${\displaystyle \vert }$例えば、アクション${\displaystyle r(d)}$そして${\displaystyle w(d)}$データ項目の読み書きと解釈される可能性がある${\displaystyle d\in D=\{1,2,3,\ldots \}}$それぞれ。次にプロセス

${\displaystyle \left(\sum _{d\in D}r(d)\cdot y\right)\vert (w(1)\cdot z)}$

価値を伝える${\displaystyle 1}$右コンポーネントプロセスから左コンポーネントプロセスへ（つまり識別子）${\displaystyle {\mathit {d}}}$値に拘束されます${\displaystyle 1}$、および無料インスタンス${\displaystyle {\mathit {d}}}$その過程で${\displaystyle {\mathit {y}}}$その値を取り）、その後マージとして動作します${\displaystyle {\mathit {y}}}$そして${\displaystyle {\mathit {z}}}$。

• 抽象化—抽象化演算子、${\displaystyle \tau _{I}}$これは、特定のアクションを「隠蔽」し、モデル化対象システム内部のイベントとして扱う方法です。抽象化されたアクションは、サイレントステップアクションに変換されます。${\displaystyle \tau }$場合によっては、これらのサイレントステップは抽象化プロセスの一部としてプロセス表現から削除することもできます。たとえば、

${\displaystyle \tau _{\{c\}}((a+b)\cdot c)=(a+b)\cdot \tau }$

これは、この場合、以下のように簡略化できます。

${\displaystyle a+b}$

イベント以来${\displaystyle {\mathit {c}}}$もはや観測不可能であり、観測可能な影響もありません。

代替および逐次合成演算子を使用して、ACP は公理^{[ 3 ]}を満たす基本的なプロセス代数を定義します。

${\displaystyle {\begin{matrix}x+y&=&y+x\\(x+y)+z&=&x+(y+z)\\x+x&=&x\\(x+y)\cdot z&=&(x\cdot z)+(y\cdot z)\\(x\cdot y)\cdot z&=&x\cdot (y\cdot z)\end{matrix}}}$

基本的な代数に加えて、2 つの追加の公理が代替演算子とシーケンス演算子、およびデッドロックアクションの関係を定義します。${\displaystyle \delta }$

${\displaystyle {\begin{matrix}\delta +x&=&x\\\delta \cdot x&=&\delta \end{matrix}}}$

マージ演算子、左マージ演算子、通信演算子に関連する公理は^{[ 3 ]である。}

${\displaystyle {\begin{matrix}x\vert \vert y&=&x\vert \lfloor y+y\vert \lfloor x+x\vert y\\a\cdot x\vert \lfloor y&=&a\cdot (x\vert \vert y)\\a\vert \lfloor y&=&a\cdot y\\(x+y)\vert \lfloor z&=&(x\vert \lfloor z)+(y\vert \lfloor z)\\a\cdot x\vert b&=&(a\vert b)\cdot x\\a\vert b\cdot x&=&(a\vert b)\cdot x\\a\cdot x\vert b\cdot y&=&(a\vert b)\cdot (x\vert \vert y)\\(x+y)\vert z&=&x\vert z+y\vert z\\x\vert (y+z)&=&x\vert y+x\vert z\end{matrix}}}$

通信演算子がプロセスではなくアクションのみに適用される場合、それはアクションからアクションへのバイナリ関数として解釈されます。${\displaystyle \vert :A\times A\rightarrow A}$この関数の定義は、プロセス間の可能な相互作用を定義します。相互作用を構成しないアクションのペアは、デッドロックアクションにマッピングされます。${\displaystyle \delta }$一方、許可されたインタラクションペアは、インタラクションの発生を表す対応する単一のアクションにマッピングされます。たとえば、通信機能では次のように指定できます。

${\displaystyle a\vert a\rightarrow c}$

これは、成功した相互作用を示しています${\displaystyle a\vert a}$行動にまで縮小される${\displaystyle c}$ACPにはカプセル化演算子も含まれています。${\displaystyle \partial _{H}}$一部の人にとって${\displaystyle H\subseteq A}$これは、通信の試みが失敗した場合（つまり、${\displaystyle H}$通信機能によって還元されていないもの）をデッドロックアクションに。通信機能とカプセル化演算子に関連付けられた公理は^{[ 3 ]です。}

${\displaystyle {\begin{matrix}a\vert b&=&b\vert a\\(a\vert b)\vert c&=&a\vert (b\vert c)\\a\vert \delta &=&\delta \\\partial _{H}(a)&=&a{\mbox{ if }}a\notin H\\\partial _{H}(a)&=&\delta {\mbox{ if }}a\in H\\\partial _{H}(x+y)&=&\partial _{H}(x)+\partial _{H}(y)\\\partial _{H}(x\cdot y)&=&\partial _{H}(x)\cdot \partial _{H}(y)\\\end{matrix}}}$

抽象化演算子に関連する公理は^{[ 3 ]です。}

${\displaystyle {\begin{matrix}\tau _{I}(\tau )&=&\tau \\\tau _{I}(a)&=&a{\mbox{ if }}a\notin I\\\tau _{I}(a)&=&\tau {\mbox{ if }}a\in I\\\tau _{I}(x+y)&=&\tau _{I}(x)+\tau _{I}(y)\\\tau _{I}(x\cdot y)&=&\tau _{I}(x)\cdot \tau _{I}(y)\\\partial _{H}(\tau )&=&\tau \\x\cdot \tau &=&x\\\tau \cdot x&=&\tau \cdot x+x\\a\cdot (\tau \cdot x+y)&=&a\cdot (\tau \cdot x+y)+a\cdot x\\\tau \cdot x\vert \lfloor y&=&\tau \cdot (x\vert \vert y)\\\tau \vert \lfloor x&=&\tau \cdot x\\\tau \vert x&=&\delta \\x\vert \tau &=&\delta \\\tau \cdot x\vert y&=&x\vert y\\x\vert \tau \cdot y&=&x\vert y\end{matrix}}}$

上記のリストにあるアクションaは値 δ を取る可能性があることに注意してください (ただし、もちろん δ は抽象化セットIに属することはできません)。