没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记164(2006)119-136www.elsevier.com/locate/entcs概率π-演算的表示Pradalier Sylvain普拉达利尔西尔万1,2 和CatusciaPalamidessi3莉克丝Ecole Polytechnique,91128 Palaiseau Cedex,France摘要在这项工作中,我们提出了一个概率扩展的π演算。 主要的新颖性是一个概率的混合选择算子,也就是说,一个选择构造的概率分布的分支,输入和输出的动作都可以发生警卫。我们开发了这个演算的操作语义,然后我们研究它的表达能力。特别是,我们比较它与子语言的两个单独的选择,其中输入和输出后卫不允许在同一个选择结构。我们的主要结果是,单独的选择可以编码混合的。 此外,我们表明,输入保护的选择可以编码输出保护的选择,反之亦然。相比之下,我们推测,他们都不能编码的两个单独的选择对。保留字:概率过程代数,表达性,编码,混合选择1介绍在并发语言领域,表达性是一个重要而有趣的问题。与顺序语言不同的是,程序的目的不仅仅是计算一个函数,而且还控制系统中各种并行组件的因此,在评估新形式主义的表达能力时,必须考虑到文献中提出的大多数主要过程演算都从表达能力的角度进行了广泛的研究,无论是在绝对意义上,即它们解决问题的能力,还是在相对意义上,即它们的比较。特别是,已经有大量的工作旨在建立不同演算之间的关系,从而为大量的形式主义1这项工作得到了INRIA ARC项目ProNoBis和INRIA DREIE′quipeAssoci′ePRINTEMPS的部分支持。2电 子 邮件地址:pradalier@lix.polytechnique.fr3电 子邮件地址:catuscia@lix.polytechnique.fr1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.07.015120S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119这是在Concurrency领域提出的。当然,这种研究的目标之一是使具有相同表达能力但能以更有效的方式实现的语言个性化。编码本身可能是有价值的,因为源语言,即使效率较低,仍然可以作为一种专用语言使用。另一个目标是找出实施的制约因素。例如,如果一种语言可以解决一个已知在分布式异步模型中无法解决的问题(例如对称领导者选举),那么我们就知道这种语言不能以完全分布式的方式实现感兴趣的读者可以在[11]中找到关于这些问题的扩展讨论然而,令人惊讶的是,对于一类重要的微积分,即概率微积分,相对表达性的问题(据我们所知)并没有得到太多的研究在几种方法中,我们提到[17]中的一种,它在精神上与我们的相似。我们建议感兴趣的读者参考[1],以获得最近对已提出的主要概率演算和模型的概述和分类。在本文中,我们向概率环境中的相对表现力研究迈出了第一步。我们重点讨论并发中的一个关键机制该构造表示在备选计算之间的选择,并且可以通过防护装置来控制。它的重要性依赖于这样一个事实,即它在分布式系统中非常有用,可以让进程进行交互和协调。人们可以根据允许出现在其中的守卫来定义各种选择运算符在进程演算中,守卫通常是通信动作(输入和输出),因此很自然地考虑以下分类:• input-guarded choice:guards只能是input actions,• output-guarded选择:guards只能是输出动作,• 单独的选择:一个选择可以包含输入或输出保护,但不能同时包含两者,• 混合选择:一个选择可以同时包含输入和输出保护。在非概率世界中,已经证明异步π演算(没有选择,只有异步输出)可以编码输入保护的选择[10]和单独的选择[9]。相反,它不能编码混合选择[11]。混合选择在CSP中也已经被证明比其他类型的选择严格更强大[3]。在这两种情况下,分离结果的证明依赖于表达某些共识问题的解决方案的能力/能力。我们有兴趣探索上述选择结构的概率扩展是否特别是,我们考虑这个问题的背景下,π演算。我们知道概率增加了表达能力:事实上,在[12]中,具有输入保护选择的π演算的概率扩展已被证明能够编码具有混合选择的π演算另一方面,这个结果本身并不能证明一切都在同一个表达类中崩溃。事实上,混合选择和概率的结合可以产生S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119121新的能力。这是探索混合选择的概率扩展的动机之一。然而,如何定义这种扩展并不明显事实上,有各种微妙的问题与并行运算符的组合性有关,如[16]中所解释的。在[15]中定义了具有混合选择的随机版本的π演算,但在这种情况下,平行算子的定义依赖于同步4假设,根据该假设,所有平行分量同时移动。这是我们从文献中所知道的概率混合选择的所有建议的情况。相反,我们想研究异步环境中选择的表现力,因为我们对分布式系统感兴趣,在分布式系统中,全局时间的假设是不现实的。1.1贡献我们提出了一个概率版本的π演算与混合选择一致的建议在[6,12]的情况下,输入保护的选择。然后,我们调查它的表达能力相对于它的子语言,这是通过限制选择结构。我们将看到,与[11]中对非概率情况的发现相反我们的结果与[12]中的结果有一些相似之处,其中混合选择使用概率输入保护选择进行编码[12]中的编码基于用餐密码协议的复杂扩展。我们认为,这样的想法不能扩展到我们的设置(这是我们关于单独选择和单一选择之间差距的猜测的一部分,见下文)。另一方面,我们也不确定我们更简单的编码是否可以以某种方式适应[12]中的设置,因为我们需要一个既有输出又有τ前缀的选择结构,这在[12]中考虑的概率异步π演算中不存在我们的结果的重要性依赖于这样一个事实,即混合选择的分布式实现比单独选择的分布式实现要困难得多在某些条件下,这甚至是不可能的。请参阅[11]关于这个主题的讨论。在层次结构的较低层,我们将展示每种形式的选择(输入保护或输出保护)可以对另一种进行目前,我们还不知道这个等级是否真的会瓦解成一种表达能力,但我们的期望是,情况并非如此:我们相信,在有两种不同选择的语言和有一种选择的两种语言之间存在着差距。我们考虑我们的语言的两个语义。第一个遵循[6]的方法,其中选择的分支上的系数加起来为1(并且对于4同步(synchronous)异步)在这里是在分布式计算的意义上使用的,即它意味着计算的底层模型是基于全局时钟的(分别是本地时钟)。这与Concurrency中的使用不同,其中同步和异步通常指的是通信。122S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119我们把它们看作概率)。第二种方法是将这些系数视为活动。然后,在执行之后,我们重新规范化与运行相关的量以获得概率。第2.3部分详细解释了这两种语义学的哲学。1.2概述:我们首先描述和解释语法和两个操作语义(第2节)。然后,我们提出了一个编码的概率混合选择的概率分开的选择(第3节)。此外,我们推测,两个单独的选择(输入和输出)不能只使用其中一个编码(第4节)。另一方面,我们证明了输入和输出保护选择可以相互编码(第5节)。然后,我们讨论了一些有争议的设计决定,我们的演算(第6节),我们的结论与未来的研究计划与这项工作(第7节)。由于篇幅的原因,我们在这里不包括证明。他们可以在[14]中找到。2具有混合选择的定量概率π-演算的运算语义在微积分中引入概率并不一定排除非决定论。事实上,由于环境、调度程序或对手而引起的行为变化可能更自然地被认为是不确定的,因为我们可能没有任何先验信息。这就是为什么,如在[6]中,我们考虑具有概率选择和经典并行运算符的语法第一个将表示由于给定调度场景中的过程而导致的行为变化。后者将产生不确定的不同调度方案。相应地,操作语义将生成与不同场景中的概率选择相对应的转换组我们称这样的一个群体为一个台阶。2.1语法我们使用的语法非常接近经典的π演算。对标准构造函数的唯一修改是在选择的每个分支上添加一个(正)系数。这是在[6,15]中使用的方法。直觉上,一个分支的系数越大,它被执行的可能性就越大。我们在第节2.3 如何从这些系数中计算概率语法由以下语法定义S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119123前缀α::=xy|x(y)|τ过程P::=<$i∈I(αi,pi).Pi |νxP|P |P|X|雷克斯X.P前缀可以是xy(输出)、x(y)(输入)和τ(无声动作)的形式一个过程可以是以下形式之一:<$i∈I(αi,pi).Pi(不同保护过程之间的加权选择),或νxP(限制),或P |Q(并行组合),或X(递归变量),或recX.P(递归过程)。我们有时写(α1,p1),P1 +. +(αn,pn).Pn而不是n≤n(αi,pi).Pi.空的和表示终止的进程,用0表示。我们的两个操作语义都使用这种语法,但对于概率语义,我们要求对于每个选择<$i≤n(αi,pi).Pi,和<$i∈Ipi是1。参见第2.3节。让我们简要回顾一下与我们的调查相关的术语:a(子)如果基数大于1的选择结构可以分别有:输出和输入,输出或输入,只有输入,只有输出,或者根本没有保护(即只有τ前缀),则语言有混合选择,单独选择,输入保护选择,输出保护选择或盲选遵循并发理论中使用的术语,我们称异步为子语言,其中输出只能由终止的过程(异步输出)跟随,并且只出现在平凡的选择中,即基数为1的选择中。换句话说,输出只能出现在xy形式的构造中。0.2.2结构叠合我们使用π演算的通常结构同余,即α-转换、平行算子的交换性和结合性、0的中性性、选择的交换性、作用域的挤压性和限制的交换性。看到”[14]这是一个明确的定义。2.3操作语义加权选择将系数与每个动作相关联。直觉上,这个系数代表行动被执行的机会:系数越高,行动的可能性越大。为了从这些系数中获得概率,它们只需要求和为1.因此,对每个系数进行重新标准化就足够了。这里我们有两种选择:我们可以直接在术语中和执行的每个步骤中对每个选择重新规范化,或者我们可以在导出传递闭包之后重新规范化124S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119μi每一个可能的步骤。这两种可能性似乎都是合理的,它们分别对应于我们的两种语义:概率语义和和定量语义。概率情况要求与每个步骤相关联的概率之和等于1,并且每个规则保持总和等于1。这两种语义的不同之处在于,在数量情况下的系数也可以用来表示其他种类的信息。例如,它可以与启用防护装置的某些反应的预期速度相关联作为例子,设P=(a1,10).P1+(a2,10).P2,Q=(b1,5).Q1+(b2,5).Q2,考虑它们的平行组合P|Q. 在概率的情况下,所有系数将D重新优化为1/2,并具有足够的可操作性。但在这种情况下,1和2更有可能首先出现。此外,b1和b2可以与a1和a2竞争,例如,如果它们都是通道上的输入动作,而通道上只有输出可用。因此,首先发生的概率可以转化为最终发生的概率。在本文中,我们也有另一个原因,考虑定量的方法:我们的主要结果,编码的概率混合选择到概率单独的选择,提出了一些问题,在概率语义的限制算子,而这个问题消失在定量语义。2.3.1两种语义在π-计算中,若P−→αQ,则P→Q. Here我们将P{−α→iP}从P到P ′ s之间的距离进行了计算。THEpiii∈Iii这种分组的原因在第2节开始时解释,我们省略了记法i∈I时没有歧义。规则CONG、SUM和REC是经典π-演算中相应规则的概率扩展合计:i(pi,μi).Pi{−→piPi}P<$PJP{−μ→iP}i.PPJ聪:piPJ{−μ→i我我我PJ}第一节记录:P[recX P/X]{−μ→iμi{\fnMicrosoftYaHei}{\fnMicrosoft YaHei}recXP{−→piPi}COM规则对应于π-π的三个经典规则的融合。S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119125我演算的交错,通信和通信与范围挤出(称为PAR,COM和关闭经典)。它比文献中的其他概率演算更复杂,因为我们处理的是异步模型(在没有全局时钟的意义上是异步的):每个进程可以以自己的速度进行,并决定是否在每个分支上同步,因此当合并两个并行进程的步骤时,可能会发生几种不同的情况μηj和QQ},我们希望从{−→pii i∈I{−→qjjj∈JP|Q. 为此,对于(PμiP, QηjQ)的随机序列,我们构造了一个−→pii−→qjjP转变|Q使用平行合成的三个经典规则之一。例如,如果PXY{−→1/2 PJ,。. }和Qx(z){−−→1/3QJ,.. . },然后从P|Q我们会我已经把我的前一个P|Q{−→τ六分之一PJ|QJ[y/z]}(坐标),以及P|QXY{−→1/6 PJ|Q,... . }(左交织),并且具有形式P |Qx(z){−−→1/6P|QJ,.. . }(右交错)。有人可能会问,为什么我们不把这些步骤放在一起,从一个单一的步骤P|Q.这是因为这三种情况之间的选择应该是非确定性的,而不是概率性的,就像经典的π演算那样条件:埃什基岛bn(μi)fn(Qj)=bn(ηj)fn(Pi)=来自条件P−→μPJbn(μ)Tfn(Q)=bn(μ)fn(Q)=经典规则PAR的λP|Q−→μPJ|Q.注意,微积分的非确定性来自这种情况。前提条件是,j.bn(μi)fn(Qj)=bn(ηj)fn(Pi)=0PμiηjCOM:{−→piPi}Q{−→qjQj}αi,j(P|Q){−−→piqjRi,j}其中,Ri,j和αi,j定义为:• 如果μi=yx,ηj=y(z),· eitherRi,j=Pi|Q_j[x/z]_i,j=τ:余项。· 或Ri,j= Pi|Q=αi,j= μi:左交织。· 或Ri,j=P|Qj∈αi,j=ηj:rightinteavingg.• 对称情况:μi=y(z),ηj=yx• 如果μi=y(x),ηj=y(z),· eitherRi,j=(νx)(Pi|Qj[x/z])= αi,j=τ:余项和余项x约束· 或Ri,j= Pi|Q=αi,j= μi:左交织。· 或Ri,j=P|Qj∈αi,j=ηj:rightinteavingg.• 对称情况:μi=y(z),ηj=y(x)• 否则,· 或者Ri,j= Pi|Q=αi,j= μi:左交织。126S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119· 或Ri,j=P|Qj∈αi,j=ηj:rightinteavingg.让我们用一个例子来说明规则COM为了简单起见,我们省略了S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119127−→−→−→−→−→−→−→{−→−→−→{−→−→−→−→{−→−→−→−→{−→−→−→−→{−→−→−→−→−→−→{−→−→−→−→{−→−→−→−→{−→−→−→−→通信中的参数。此外,如果在一个步骤中,我们有两个具有相同标签和相同延续的转移,那么我们只写一次转移,当然概率等于概率之和例2.1证明了P=(1/2,y),P1+(1/2,x),P2和Q=(1/3,y)的关系。Q1+(2/3,z). 问题2.P的最大值为|问题24,如果P的第一个分支和第一个分支的组合产生了3个P的不同结果,Q的第一个,P的第一个和Q的第二个,P的第二个和Q的第一个,P的第二个和Q的第二个,P的第二个和Q的第二个。所有可能的步骤是:P|Qy{−→1/2 P1|Q,−→x二分之一P2|Q}P|Qy1/2P1 |Q,x1/6P2 |Q,z1/3P|Q2}P|Qy{−→1/2P1|Q,−→x1/3P2|Q,y1/6P|Q1}P|Qy y1/2P1 |Q,1/6P|Q1,−→z1/3P|Q2}P|Qy{−→1/6 P1|Q,−→z三分之一P|Q2−→x二分之一P2|Q}P|Qy1/6P1 |Q,z1/3P |Q2,x1/6P2 |Q,z1/3P|Q2}P|Qy{−→1/6P1|Q,−→z1/3P|Q2−→x1/3P2|Q,y1/6P|Q1}P|Qy1/6P1 |Q,z1/3P |Q2,y1/6P |Q1,z1/3P|Q2}P|Qy1/3P1 |Q,y1/6P |Q2,x1/2P2|Q}P|Qy y1/3P1 |Q,1/6P|Q2−→x1/6P2|Q,−→z1/3P|Q2}P|Qy1/3P1 |Q,y1/6P |Q2,x1/3P2 |Q,y1/6P|Q1}P|Qy y y1/3P1 |Q,1/6P |Q2,1/6P|Q1,−→z1/3P|Q2}P|QP|Qy{−→1/6y{−→1/6P|Q1,P|Q1,−→z−→z三分之一三分之一P|Q2、P|Q2−→x−→x二分之一六分之一P2|Q}P2|Q,−→z三分之一P|Q2}P|Qy1/6P |Q1,z1/3P |Q2,x1/3P2 |Q,y1/6P|Q1}P|Qy{−→1/6P|Q1,−→z1/3P|Q2,y1/6P|Q1,−→z1/3P|Q2}P|Q{−→τ1/6P1|Q1,y1/3P1|Q,P|Q{−→τ1/6P1|Q1,y1/3P1|Q,−→x1/2P2|Q}−→x1/6P2|Q,−→z1/3P|Q2}P|Qτ1/6P1|Q1,y1/3P1 |Q,x1/3P2 |Q,y1/6P|Q1}P|Q{−→τ1/6P1|Q1,y1/3P1|Q,y1/6P|Q1,−→13P|Q2}z/P|Q{−→τ1/6P1|Q1,P|Q{−→τ1/6P1|Q1,−→−→z1/3P|Q2−→z1/3P|Q2−→−→x1/2P2|Q}−→x1/6P2|Q,−→z1/3P|Q2}P|Q{−→τ1/6P1|Q1,−→z1/3P|Q2−→x1/3P2|Q,y1/6P|Q1}P|Qτ1/6P1|Q1,z1/3P |Q2,y1/6P |Q1,z1/3P|Q2}2.3.2两个V规则前面的四条规则对于两种语义都是相同的但是,由于限制可以消除某些动作{−→{−→{−→128S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119(如果x∈fn(μ)<$$>(μ=zx<$z/=x),则νx阻止P做μ),因此在概率情况下,必须重新规范化系数,以便sum保持等于1。在定量的情况下,擦除不满足条件的跃迁而不修改系数是足够的。至于规则COM,这两个规则中的每一个都对应于经典π-演算的几个规则。在每个规则中,第一个集合用于输出S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119129νx.Pi我νx.Pi我Pi)的值Pi)的值n=0Pi)的值名字由v约束。第二个集合是不涉及任何被v约束的名字的动作。这些对应于经典规则OPEN和NU。定量案例μiν:P{−→piPi}i。(x∈/fn(μi)<$(μi=zx<$z/=x))qz(x){−→piPi,μi=zix,zi/=x}μi{−→piνxPi, x∈/fn(μi)}疑似病例概率情况下的规则是从前一个通过重新规范化的系数。μν:P{−→piPi}i。(x∈/fn(μi)<$(μi=zx<$z/=x))pz(x){−→qiPi,μi=zix,zi/=x}μ{−→qiνxPi, x∈/fn(μi)}我是一个很好的朋友。qi=pi/(μj:x∈/fn(μj)<$(μj=zx<$z/=x)pj)注意,除了用于定量情况的νq因此,在概率的情况下,我们只导出系数之和等于1的步骤。2.4弱步弱步骤的定义如下:wea1:μiP{−→piPi}μ=piPi}μiτηjwea2:P{=piPi}{=qQ}Q{=rjRj}μ=piPi}ηj{=q. RJ Rj}wea3:P{μiPi}limn→∞皮因=piμ=piPi}130S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119131前两条规则的灵感来自[5]。最后一个是新的,代表第二个的极限情况。请注意,限制只涉及概率,最后一条规则非常重要,因为我们的编码是基于一个循环,每当我们做出错误的决定时,它允许回溯。最终,正确的决定将以概率1做出,但这可能只发生在极限情况下注意,这里系数的和也保持不变。3混合选择的分离选择编码我们将证明,在没有nu算子的概率π-演算和定量π-演算中,混合选择是可由单独的选择编码的。在这两种情况下,我们证明了我们的编码的正确性,它保留了一种弱互模拟。 我们之所以写 是因为目前我们同态地平移它是不可行的,因为规则νp所引起的再正规化干扰了弱步骤。我们将在第3.2.1节中更详细地解释这个问题。3.1编码我们的编码是同态w.r.t.除了选择之外的所有构造函数因此,我们只解释选择的编码 设P是一个混合选择,P i∈I( pi, xiyi),Pi+<$j∈J(qj,τ),Qj+<$k∈K(rk,xk(zk)),Rk.如果I或K为空,则选择不是混合,[P]] =P。否则,我们将在对应于输出、输入或τ的在每个分支中,我们在输出、输入或τ之间进行(单独)选择。例如,当一个人可以进入输出分支时,即使上下文在输入上强制通信,我们也必须包括一个回溯机制为此,单独的选择也包含一个递归返回到开始的τ-前缀分支,概率为1,需要小于1。这意味着该过程原则上可以永远循环。然而,这样的事件将有概率与自身无穷多次乘积,即0。3.1.1加权混合选择[[νx.P]]=νx。[[P]][[P|Q]]=[[P]]|[[Q]][[rexX.P]]= recX.[[P]][[X]] =X设P是一个混合选择,其形式为:Pi∈I(pi,xiyi).Pi+<$j∈J(qj,τ).Qj+<$k∈K(rk,xk(zk)).Rk.我们定义P的编码如下:132S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119二分之一1/ 41/ 41/ 21/ 2[[P]]= recX. ((i∈I(pi),τ).P发送+(<$j∈J(qj),τ).Pτ+(k∈K(rk),τ).P接收)其中:P=0(pi(1 − 1),x y)。[[P]]+(π,τ).X发送i∈Ii∈I(pi) ii iPτ=j∈J(qj(1 − τ),τ)。[[Q]]+(τ,τ).X<$j∈J(qj)jP=0(rk(1−k),x(z))。[[R ]]+(τ,τ).X接收k∈Kk∈K(rk)k k k3.2编码的正确性3.2.1证明的结构在概率情形下,我们用定理3.5和3.6证明了编码的正确性;在定量情形下,我们用定理3.7和3.8证明了编码的正确性。在这两种情况下,定理对应于一种弱互模拟。定理3.5和3.7正好对应于弱互模拟的一个方向。他们说,如果P可以执行一个步骤,那么[P]可以执行相应的弱步骤。为了证明这些结果,我们使用引理3.2。从本质上讲,这个引理的i-v点所陈述的性质表明,规则SUM、REC、CONG、COM和νq的弱变体分别相对于规则wea 1、wea 2和wea 3(即=ω的定义)是合理的。这里的ob tai nedbyyreplacing−→w ith=inX.不幸的是,同样的结果并不适用于规则νp。以下是一个反例。E x示例3.1L etP=(1/2,c)。0+(1/2, τ)。X和dX=(1/2,b)。0+(1/2,a)。0的情况。WehaveP{−→c0,=<$b0,=a<$0}. IfthequivalentofLemma3. 二、vforvpweretoo好吧,新的房子都很安静。P{cb0}(计算器已定义)=2/ 30, =三分之一从νq的情况,因为我们需要应用重整化)。然而,我们只有这一点。P{−→c0,−→τνa. X}和dνa. X{−→b10},由Rulea2我们你可以去那里。P{cb0}。=1/ 2 0, =二分之一上述反例所说明的差异是由于规则SUM-COM的弱变体中的重整化将在与规则weak 1-weak 3不同的时间发生。引理3.2S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119133=piJJK K=pi{τqj我ηjηji. 若Q{−→qjQj}可由任意SUM导出,则Q{=qjQj},μi μiX=piiX=piiiii. 若P<$PJ,则P{μiP}和μi.PPJ,则PJ{μiPJ},=piiii=piiiv. 如果P{μiηjP},Q{Q},m,j.bn(μ)fn(Q)=m和bn(η)fn(P)==pi我 αi,j=qjjij jiP,ten(P|Q){={piqjRi,j},其中αi,j和R i,j在COM规则,v. 如果P{μiP}和d∈i. (x∈/fn(μ)<$(μ=zxzx)),则νx.Pzi(x)=pi ii ii{=piμi我我我=pii ii在另一个方向上,为了得到一个标准的弱互模拟,我们应该有,如果[P]可以执行一个步骤,那么P可以执行相应的弱步骤。然而,我们不能得到这样的结果:由于翻译将一个混合选择分成了各种不同的选择,我们在翻译项中得到的可能性比在原文中得到的更多。实际上,由于翻译项只能进行盲选,为了得到标准互模拟,我们需要通过互模拟将编码产生的Psend、PreceiveetPτ与P相这不起作用,人们可以很容易地看到,这些条款在一般步骤不同的初始条款。然而,[P]可以执行的所有弱步骤都可以继续,以便得到包含在P的步骤中的步骤。例如,在[P]执行了盲选之后,它可以执行输出选择,这将导致m[P]]{xiyi[[Pi]]}{−→τqPτ}{−→τrP个接收 }。 通过重复这一点,对于另外两种分支,我们将得到形式为trP{xiyiPi}=jQ}xk(zk){=rkRk},这正好对应于P的步长。这种情况在经典(非概率)设置中是众所周知的:通常情况下,编码在每个步骤都不保留操作语义。换句话说,可能发生的是,编码过程的计算中的一些中间状态不对应于原始过程的任何衍生物的编码。然而,通常情况下,编码满足一个属性,μJμτ如下形式:如果[P]]=<$Q,则存在P 这样,[P]]=Q=JμJ[[P]]和P=P。为了在概率设置中形式化上述想法,我们引入步骤完成定义3.3设P是一个过程,μi{−→pi Pi}是其步骤之一。一完成这一步是一个薄弱的步骤,导致推导开始于awea1应用于Pwea2和wea3。μ{−→pi Pi},然后继续连续应用直觉上,完成一个步骤意味着探索这个步骤的可能延续,每次我们得到一个τ时就更深入。wea3规则实际上只修改了coe,wea2规则只允许扩展无声的转换。因此134S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119KKK在每个分支中,一个步骤的完成不会比第一个非静音动作更进一步。我们注意到,完备化的概念是相当健壮的,因为它并没有减少交互的可能性,如下面的命题所示命题3.4设P是一个过程。 设Pηjμi{−→piP1}是其步骤之一,并且设P {=<$qj Qj}是它的一个完备化。现在考虑一个过程R,令αR{−→ rkRk}为e个步骤。 Le t Xeastefthe fff frmP|R{. . . }obtainedby将COM规则应用于Pμi{−→pi Pi}和Rα{−→rk Rk}。 通过使用引理iv,ηj前提P{=qjQj}和Rα{−→rk Rk},我们得到形式为P的步长Y |R{.. . }也就是X的完备化我们现在准备完成对编码正确性的正式评估:定理3.6和3.8代表互模拟的另一个方向,但只是“模完成”。更确切地说,他们指出[P]]的每一步都可以完成为与P之一相对应的一步。3.2.2概率情况下的正确性结果定理3.5在概率语义中,如果PμiP}可以在没有使用该规则v,该n[[P]]{μi p[[P]]}。{−→piip=i i定理3.6在概率语义中,若[[P]]μiP},则存在Q{−→piijηjηj因此,[[P]]{=qj[[Qj]]}是一个与B和P{=qj}完全相同的概念Qj}。3.2.3定量情况的正确性结果问题3.7在本问题中,如果PμiP},则n[[P]]{μi p[[P]]}。{−→pii=ii定理3.8在数量语义中,若[[P]]μiP},则存在Q{−→piijηjηj因此,[[P]]{=qj[[Qj]]}是一个与B和P{=qj}完全相同的概念Qj}。3.3将单独选择的大小减少到两个这种编码将语言简化为一种非常简单的独立选择形式:盲选择和大小为2的选择,其中一个分支以τ为前缀。编码的工作方式与前一个完全相同。我们将单独选择的每个分支分开,就像我们将输入与输出和τ分开一样。正确性定理是相同的。S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119135[[i∈I(pi,μi).Pi]]=recX. ()i∈I(pi,τ).Qi式中:Qi=(1 −,μi)。[[Pi]]+(π,τ).X4单独选择我们刚刚展示了如何将混合选择简化为大小为2的单独选择。现在的问题是将两个独立选择的对与只有一个(通常是[6]中提出的概率异步π演算我们推测,这两个独立的选择中的一个没有编码。注意,第5节的编码证明了输入保护选择和输出保护选择是等价的。因此,我们可以限制比较这对单独的选择输入保护的选择。4.1尝试对不同的选择我们在这里提出了我们最好的尝试,通过输入保护选择来编码单独的选择,我们讨论了为什么它不起作用,我们推测不可能定义这样的编码。在一个非概率的设置,各种选择已编码使用并行运算符。其基本思想是将选择的分支并行放置,确保只有其中一个分支会被执行。例如,见[10,9]。然而,这个想法在这里不能工作,因为过渡将不再处于同一步骤。换句话说,我们不能用平行性来编码选择,因为在选择中,两个分支之间的决定是由概率决定的,而在平行乘积中,它是由非决定论决定的。因此,一个选择只能转化为另一个类似于行动和概率的选择。因此,我们唯一的希望是将单独的选择转换为输入保护的选择。例如,让我们使用[7]的思想将输出前缀转换为输入和异步输出:[[x(y).P]]= νz(xz| z(y)。[[P]])[[xy.Q]]= x(z). (zy |[[Q]])这种编码可以通过以下方式提升到选择:136S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)119[[(p,x(y)).Px+(1−p,τ).Pτ]]=VZ(XZ|(p,z(y))。[[Px]]+(1 − p,τ)。[[Pτ]])[[(px,xy).Px+(1−px,τ).Pτ]]=(px,x(z))。(zy|[[Px]])+(1 − px,τ)。[[Pτ]]然而,这不起作用,因为输出保护选择的转换可以与xz同步,而同时输入保护选择的转换可以执行其τ。输入选择执行了它的τ,但输出选择开始了它的同步分支,没有办法倒退。由于我们没有输出选择,以前编码的向后机制不能用于输出。 输出保护选择的转换现在处于死锁状态,这在原始术语中是不可能的。一种解决方案可以是将输入选择的平移的τ替换为通道x上的输入,使得xz可以与该分支同步,或者其中输出的转换的输入分支被保护选择。但是x上的另一个输入保护选择可能会干扰。它还包含一个xzJ,可以由第一个输入保护选择接收,而xz将由输出保护选择。 在这里,我们又一次遇到了意外的僵局。5输入和输出保护选择之间的编码最后,我们提出了输入和输出保护的选择之间的编码。我们使用在前一节中已经说明的[7这些编码突出了两种选择之间的对称性,并确立了它们同样具有表达力。必须注意的是,编码只使用异步输出(尽管它们可以在选择中使用)。因此,所有四种有输入或输出选择的语言,以及有无异步输出的语言都是等价的。将输入保护选择编码为输出保护选择[[i∈I(pi,xi(yi)).Pi]]=(νzi)i∈I(i∈I(pi,xizi))|i∈Izi(yi). [[Pi]])[[xy.P]]= x(z). (zy|[[P]])S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)1191371/ 4 1/ 41/ 2将输出保护选择编码为输入保护选择[[x(y).P]]= νz(xz|z(y)。[[P]])[[i∈I(pi,xiyi).Pi]]=i∈I(pi,xi(z)).(zyi|[[Pi]])6关于我们微积分设计的讨论在我们语言的设计中,我们采取了一些设计决策,这些设计决策与同步通信演算的选择性质(在并发理论的意义上)严格相关,例如CCS [8],TCSP [4]和ACP [2],除了π演算。在这些演算中,对选择中某个分支的承诺与转换同时发生,并与沟通行动的合作伙伴达成一致。换句话说,在另一个伙伴决定做什么之前,一个伙伴不可能承诺一个通信动作。因此,这些语言中的选择是无记忆的。为了说明这一点,请考虑Roberto Segala在一次讨论中提出的以下例子:• P=(1/2,a)。0 +(1/2,b)。0• Q= recX((1/2,a). X+(1/2,c)。X)可能的步骤P|Q是:P|Q{−→τQ,−→aP|Q,−→cP|Q}如果通信没有发生,则系统P|Q保持在同一状态。因此,通过总是调度上述步骤,我们有一个计算,其中通信最终以概率1发生。关键点是上面的例子是,不可能对某个通信动作进行单边提交,并且在随后的转换中保持对这种提交的记忆。事实上,如果同步没有发生,那么可能是P试图制造b的情况。但是在下一步骤,我们可以重新调度该同步步骤(具有同步时间的1/4的可能性),而不考虑P在先前的转换中已经选择了b的事实由于法律没有发现这种可访问性:在P中,同步概率为1/2,因此他认为不应该存在信道a上的同步以大于1/2的概率发生的上下文。我们认为,上下文可以增加通信事件发生的概率,这是完全合理的,并且符合并发理论中同步通信的哲学。因此,在上面的例子中,我们发现通信最终以概率1发生是138S. 普拉达利耶角Palamidessi/Electronic Notes in Theoretical Computer Science 164(2006)1197今后工作我们感兴趣的是证明(或证伪)我们的猜想(见第4部分)。目前,我们正在寻找一些不可能的结果,概率系统的
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WPF渲染层字符绘制原理探究及源代码解析
- 海康精简版监控软件:iVMS4200Lite版发布
- 自动化脚本在lspci-TV的应用介绍
- Chrome 81版本稳定版及匹配的chromedriver下载
- 深入解析Python推荐引擎与自然语言处理
- MATLAB数学建模算法程序包及案例数据
- Springboot人力资源管理系统:设计与功能
- STM32F4系列微控制器开发全面参考指南
- Python实现人脸识别的机器学习流程
- 基于STM32F103C8T6的HLW8032电量采集与解析方案
- Node.js高效MySQL驱动程序:mysqljs/mysql特性和配置
- 基于Python和大数据技术的电影推荐系统设计与实现
- 为ripro主题添加Live2D看板娘的后端资源教程
- 2022版PowerToys Everything插件升级,稳定运行无报错
- Map简易斗地主游戏实现方法介绍
- SJTU ICS Lab6 实验报告解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功