Álgebra de procesos comunicantes

ACP utiliza acciones instantáneas y atómicas (${\displaystyle {\mathit {a,b,c,...}}}$) como sus primitivos. Algunas acciones tienen un significado especial, como la acción${\displaystyle \delta }$, que representa un punto muerto o estancamiento, y la acción${\displaystyle \tau }$, que representa una acción silenciosa (acciones abstractas que no tienen una identidad específica).

Las acciones se pueden combinar para formar procesos utilizando diversos operadores. Estos operadores se pueden clasificar, a grandes rasgos, en operadores que proporcionan un álgebra de procesos básica , concurrencia y comunicación .

• Elección y secuenciación : los operadores algebraicos más fundamentales son el operador alternativo (${\displaystyle +}$), que ofrece una opción entre acciones y el operador de secuenciación (${\displaystyle \cdot }$), que especifica un orden en las acciones. Así, por ejemplo, el proceso

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

primero elige realizar cualquiera de las dos${\displaystyle {\mathit {a}}}$o${\displaystyle {\mathit {b}}}$y luego realiza la acción${\displaystyle {\mathit {c}}}$. Cómo la elección entre${\displaystyle {\mathit {a}}}$y${\displaystyle {\mathit {b}}}$No importa cómo se haga y se deja sin especificar. Nótese que la composición alternativa es conmutativa, pero la composición secuencial no lo es (porque el tiempo fluye hacia adelante).

• Concurrencia : para permitir la descripción de la concurrencia, ACP proporciona los operadores merge y left-merge . El operador merge,${\displaystyle \vert \vert }$, representa la composición paralela de dos procesos, cuyas acciones individuales se entrelazan. El operador de fusión izquierda,${\displaystyle \vert \lfloor }$, es un operador auxiliar con una semántica similar a la de la fusión, pero con el compromiso de elegir siempre su paso inicial del proceso de la izquierda. Como ejemplo, el proceso

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

pueden realizar las acciones${\displaystyle a,b,c,d}$en cualquiera de las secuencias${\displaystyle abcd,acbd,acdb,cabd,cadb,cdab}$Por otro lado, el proceso

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

solo puede realizar las secuencias${\displaystyle abcd,acbd,acdb}$ya que los operadores left-merge aseguran que la acción${\displaystyle {\mathit {a}}}$ocurre primero.

• Comunicación : la interacción (o comunicación) entre procesos se representa mediante el operador de comunicaciones binario,${\displaystyle \vert }$. Por ejemplo, las acciones${\displaystyle r(d)}$y${\displaystyle w(d)}$podría interpretarse como la lectura y escritura de un elemento de datos.${\displaystyle d\in D=\{1,2,3,\ldots \}}$, respectivamente. Luego el proceso

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

comunicará el valor${\displaystyle 1}$del proceso del componente derecho al proceso del componente izquierdo ( es decir, el identificador)${\displaystyle {\mathit {d}}}$está ligado al valor${\displaystyle 1}$y instancias gratuitas de${\displaystyle {\mathit {d}}}$en el proceso${\displaystyle {\mathit {y}}}$tomar ese valor), y luego comportarse como la fusión de${\displaystyle {\mathit {y}}}$y${\displaystyle {\mathit {z}}}$.

• Abstracción : el operador de abstracción,${\displaystyle \tau _{I}}$es una forma de "ocultar" ciertas acciones y tratarlas como eventos internos a los sistemas que se están modelando. Las acciones abstractas se convierten en la acción de paso silencioso.${\displaystyle \tau }$En algunos casos, estos pasos silenciosos también pueden eliminarse de la expresión del proceso como parte del proceso de abstracción. Por ejemplo,

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

que, en este caso, se puede reducir a

${\displaystyle a+b}$

desde el evento${\displaystyle {\mathit {c}}}$Ya no es observable y no tiene efectos observables.

Utilizando los operadores de composición alternativa y secuencial, ACP define un álgebra de procesos básica que satisface los axiomas ^{[ 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}}}$

Más allá del álgebra básica, dos axiomas adicionales definen las relaciones entre los operadores alternativos y de secuenciación, y la acción de interbloqueo ,${\displaystyle \delta }$

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

Los axiomas asociados con los operadores de fusión, fusión izquierda y comunicación son ^{[ 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}}}$

Cuando el operador de comunicaciones se aplica solo a acciones, en lugar de a procesos, se interpreta como una función binaria de acciones a acciones,${\displaystyle \vert :A\times A\rightarrow A}$. La definición de esta función define las posibles interacciones entre procesos : aquellos pares de acciones que no constituyen interacciones se asignan a la acción de interbloqueo,${\displaystyle \delta }$, mientras que los pares de interacción permitidos se asignan a acciones individuales correspondientes que representan la ocurrencia de una interacción. Por ejemplo, la función de comunicaciones podría especificar que

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

lo que indica que se ha producido una interacción exitosa.${\displaystyle a\vert a}$se reducirá a la acción${\displaystyle c}$. ACP también incluye un operador de encapsulación,${\displaystyle \partial _{H}}$para algunos${\displaystyle H\subseteq A}$, que se utiliza para convertir intentos de comunicación fallidos (es decir, elementos de${\displaystyle H}$que no se han reducido a través de la función de comunicación) a la acción de interbloqueo. Los axiomas asociados con la función de comunicaciones y el operador de encapsulación son ^{[ 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}}}$

Los axiomas asociados con el operador de abstracción son ^{[ 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}}}$

Tenga en cuenta que la acción a en la lista anterior puede tomar el valor δ (pero por supuesto, δ no puede pertenecer al conjunto de abstracción I ).