首页 理论教育 Pi演算的语法定义及应用研究

Pi演算的语法定义及应用研究

时间:2023-10-31 理论教育 版权反馈
【摘要】:“Prefix:τ.P”表示执行τ动作后执行进程P,τ被称作哑前缀,表示进程内部不可见的动作。“Prefix:.P”表示通过以命名的通道输出名字x,然后执行进程P,叫作否定前缀,被视为一个包含x的输出端口。由此,可以将Pi演算语法定义如下:以上操作的优先级关系如下:因此,P|τ.Q+R等价于+R。对于Pi演算中的一个进程P,其所有名字组成的集合记为n,其中包括自由名和受限名。图3.2图示因此,有如下等式:

Pi演算的语法定义及应用研究

设P、Q、R代表进程,其中:

(1)“Summation:0”表示进程结束。

(2)“Prefix:τ.P”表示执行τ动作后执行进程P,τ被称作哑前缀,表示进程内部不可见的动作。

(3)“Prefix:a(x).P”表示在以a命名的通道下接收任意一个名字z,然后执行进程P{z/x}(P{z/x}表示将P中的名字x替换成接收的名字z),其中a(x)被称作肯定前缀,a被视为一个输入端口,名字x被肯定前缀a(x)所绑定。

(4)“Prefix:img.P”表示通过以img命名的通道输出名字x,然后执行进程P,img叫作否定前缀,img被视为一个包含x的输出端口。

(5)“Summation:P+Q”表示执行进程P或Q其中一个进程,并且只能执行一个进程,当有两个以上进程时,也可表示为img(这里的集合I是有限集)。

(6)“Composition:P|Q”表示并行执行P和Q两个进程,这两个进程相互独立,并且这两个进程也可以通过通道彼此进行交流,如果进程P(或Q)在任意输出端口img有输出动作,那么同时进程Q(或P)也可在同一通道a上有接收动作,P和Q之间还可以发生内部哑操作。

(7)“Match:[x=y]P”表示如果名字x与名字y是完全相同的,则执行进程P,否则为空进程,不做任何动作。

(8)“Restriction:(vx)P”表示将名字x限制到进程P中使用,x是P的私有名字。

(9)“Defined:A(z1,…,zn)”表示对于标识符A,必须存在唯一的定义等式img,其中名字x1,…,xn互不相同并且在P中都是自由名,满足以上条件就执行进程img(定义等式提供了一个循环,因为进程P可以包含任意标识符,甚至A本身)。

由此,可以将Pi演算语法定义如下:

以上操作的优先级关系如下:

因此,(vx)P|τ.Q+R等价于(((vx)P)|(τ.Q))+R。(www.xing528.com)

对于Pi演算中的一个进程P,其所有名字组成的集合记为n(P),其中包括自由名(Free Occurrence of Name)和受限名(Bounded Occurrence of Name)。自由名组成的集合记为fn(P),受限名组成的集合记为bn(P),且bn(P)=n(P)-fn(P)。

下面给出一些相关定义:

(1)称名字w对进程P是新鲜(Fresh)的,w∉n(P)。

(2)自由名的代入:对任何进程P,进程P{z/x}是将P里每个自由出现的x改为z而得到的进程,称为在进程P里对自由名x进行代入。

(3)受限名的改名:①对进程a(x).P的受限名x,如果z∉fn(P),可用z改名并将改名结果记为a(z).P{z/x};②对进程(vx)P的受限名x,如果z∉fn(P),可用z改名并将改名结果记为(vz)P{z/x}。

其中,对a(x).P或(vx)P改名的结果并不导致a(x).P或(vx)P里的任何名字的自由出现变为受限出现;为防止改名失败,可简单地使用新鲜名字来改名。

如果P、Q、R三个进程都包含自由名x,可以用图3.1表示P|Q|R。

图3.1 P|Q|R图示

如果P、Q、R三个进程共享的名字x是受限名,可以用图3.2表示(vx)(P|Q|R)。

图3.2 (vx)(P|Q|R)图示

因此,有如下等式:

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈