没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记41 No.3(2000)网址:http://www.elsevier.nl/locate/entcs/volume41.html第50-69页First–order迈克尔·巴尔达穆斯卡尔斯鲁厄大学计算机设计与容错研究所baldamus@ira.uka.de摘要上下文互模拟是高阶过程的一种概念上吸引人的行为等价. 假设名称或通道的作用域规则是静态的,这个概念可以用所谓的正常互模拟和π演算互模拟来描述。本文提供了一个新的表征。具体地说,在静态设置的后期上下文互模拟的特点是普通的延迟互模拟。其基础是一种新的高阶流程操作语义,其中高阶通信被触发器操作的耦合所 在原始语义中,只要发生输入或输出,这些动作就会新鲜生成。为了获得表征,这些动作必须被归一化;为了实现这种归一化,反过来,使用了一种新的移位和不移位动作的方案1介绍互联并发进程系统的数学研究有广泛的可能的一个特别有趣的是移动性,其中进程可以重新定位和/或通信拓扑可以动态变化。在进程代数领域,π演算[13]被发明来描述和分析动态变化的通信拓扑所带来的移动性;高阶进程和移动环境[6]被引入来描述和分析进程重新定位。这里,重点是高阶过程。这种方法可以追溯到[3];它是由随后的工作开始的,[1]本文所介绍的材料是作者在柏林工业大学担任FLP/KIT研究小组成员时开发的。作者由ElsevierScienceB提供200 0个用户。 V. 操作访问和C CB Y-NC-ND许可证。50阿尔达穆斯51[19]第10段。 这个想法是赋予进程发送和接收自己的同类的能力。这一规定使过程成为一等公民;因此,我们有理由称之为“高阶”过程。标准的进程代数方法学要求研究从操作语义学中导出的行为前序和等价关系至于更例如,名称或通道的动态和静态作用域原则之间存在区别动态作用域意味着进程传递不会调用α-转换,因此传递的进程的自由名称或通道至于高阶过程上的行为前序和等价这个概念避免了我们在高阶互模拟的情况下看到的过度歧视(参见。[17],一个概念研究[19]和相关的作品。 一个理论上的替代方法是De Nicola/Hennessy风格的测试[7],适用于高阶过程。然而,这个概念可能比互模拟要复杂得多假设作用域规则是静态的,上下文互模拟可以根据正常互模拟[17]和π演算互模拟[18]来表征,其中后一个表征涉及从高阶到π演算过程的语法翻译。这些结果很有趣,因为它们基本上将静态环境中的高阶通信减少这个想法是,在这种情况下,高阶通信可以被理解为一种生成要发送的进程副本的机制,这些副本在概念上不会改变位置,因为作用域规则是静态的。除了副本的生成之外,所有发生的事情都是由接收上下文触发的因此,本文的主要目的是以一种新的方式表征上下文互模拟,即严格意义上的延迟互模拟。 这个结果仍然坚持将高阶通信减少到一阶通信的想法。它与上面提到的主要区别在于,根据[9]的延迟互模拟不位于高阶水平,例如正常互模拟,或π演算水平。除了这种简单性之外,这种表征还应该允许人们将许多结果和技术从类CCS过程的世界或第5节)。所有这一切的技术基础是一种新型的结构化操作语义(SOS),用于具有静态作用域的高阶流程。最值得注意的是,将高阶通信减少到一阶通信的想法是通过从一开始就省去进程传递来实现的。为此,SOS将要发送的进程放入复制器上下文中,而不是发送它们,阿尔达穆斯52第二,它不包含一个通信规则,但耦合规则的触发动作;第三,它采用了一个移位和unshifting计划规范化新鲜生成的触发动作。因此,这里技术上的新的一部分是生成副本和触发器的这些现有的正常和π演算互模拟方面的特征还应该注意的是,新鲜名称的规范化是π演算模型的一个组成部分这些模型总是考虑相对于名称上下文的进程,因为名称规范化取决于π演算进程的自由名称与此相反,这里介绍的移动和不移动的方案并不受任何类似的影响;因此,它允许我们以通常的方式进行,即通过考虑过程本身。本文件的结构如下:• 第2节通过介绍一种语言、一个标准SOS以及上下文和高阶过程的正常互模拟的概念来提供背景。• 第三节介绍了上述新的SOS• 第4节介绍了第3节中的新SOS上的延迟互模拟的概念• 第五节总结全文,并对SOS和特征定理的应用进行了展望具体来说,它简要地提到了一个完全抽象的最终余代数语义与这种语义是基于第3节中的SOS,它的完全抽象性是在特征理论的帮助下证明的。由于空间的考虑,大多数证明都被省略了。他们都可以在[4]中找到。确认在此,作者感谢匿名审稿人对本文的评论和建议。2背景本节介绍一种语言,一种具有静态作用域的SOS,以及上下文和高阶过程的正常互模拟的概念阿尔达穆斯53Σ−→--T I(Var):P ::= i∈I prei. P i|P1|P2|P\a o|!P|XI|FP前(变量):前::=aI|a我|n|一阶前缀| aII? XI|a二等!PT II(Var):F ::= YII|λXI. P表1BNF–like grammar for higher–order processes, where2.1语言严格地说,接下来要介绍的微积分是然而,它与大多数有关文献中提到的高阶过程是一致的然后,该语言以类似BNF的方式由表1结合表2给出元素I和II分别用于指定一阶和高阶实体。具体地说,I伴随着(普通的)一阶通道,用于单纯的同步,以及类型进程的变量; II伴随着二阶通道,用于进程传递,以及类型进程的变量。这些下标有时被省略,因为它们在上下文中很清楚通道和变量或命令I或II必须通过两个相互不相交的,可数无限集chI和chII,并通过两个可数无限集VarI和VarII。语言包含一阶通道,因为它们是第3节中介绍的新SOS所必需的另一种成分需要-SOS的假设是在一阶信道位置使用自然数的可能性。在这个角色中,它们充当标准化通道。因此,假设ch I和N(包括零的自然数的集合)是不相交的。这是有意的,因为该假设,归一化信道不能被限制构造函数基本上与Sangiorgi的高阶π -演算相同[16])没有任何π特别是,求和必须是有保护的,因为高阶过程上的弱行为等价在一阶框架内(cf. [12])。此外,XI在P中的抽象表示为λXI。P,并且P2P是类型为((process−→ process)×process)−→process的应用构造函数。为了完成这一小节,应该注意的是,P\ao在P中绑定ao,o∈I,II,并且aII?XI. P和λXI. P在P中结合XI。替换总是调用α(一阶)项P的自由一阶通道的集合阿尔达穆斯54类定义术语/说明典型变量ChI(给定)first–ordera I,b I,.第二章(给定)higher–ordera II,b II,.ChI{aI:aI∈ChI}互补一aI,b I,.N(给定)正规化通道n,m,.. .N{n:n∈N}互补正规化信道n,m,.瓦尔奥(给定)O阶变量X o,Y o,.Var瓦尔一世变量V,W,.TI(Var)见表1first–orderP,Q,.前(变量)见表1前缀词预TII(Var)见表1higher–orderF G...T(变量)TI(Var)TII(Var)方面T,U,...主题I内奇岛first–order我,我,...SubjII第二章高阶学科s II,t II,.表2句法类及其典型变量,o∈{I,II}。2.2SOS表3中的公理和规则这是一个SOS的风格[2,5],因为过程传输是通过将接收上下文转换为抽象并将此抽象替换为发送上下文来实现的为此,高阶输出预固定公理(out-HO)和通信规则(com)与传统框架中的对应公理不同 具体来说,((YII)|P2,其中YII是任意(高阶)变量,P 1是过程发送,P 2是输出残差;(com)做了已经提到的事情。从技术上讲,YII的选择是任意的;原因是我们只考虑其源项不包含自由变量在另一个技术注释中,静态作用域是通过(com)和(app)调用普通替换来实现的,这意味着被替换到输入上下文中的进程和被替换到输出上下文中的输入上下文永远不会捕获它们的自由名称SOS在各种动作集上运行。 其定义和典型阿尔达穆斯55−→−→(YKK1O12121我II12我我 12O类定义典型变量第一幕ChI∪ ChI∪ N∪ NαI,...第二幕Ch II?第二个!VarIIαII,...法第一幕第二α,.. .第一幕 τ第一µI,ηI,.action=cho(action)=defaI/aI.{aI}ifo=I如果o=II,n/n∅二级?X I/AII!YII.如果o=I,{aII}如果o=II预(pre) pre. P P如果pre不是(out)aII!P1.P2a二等!YIIII(1)|P2µ(choice)(选择)Pk−→PJ1蕴含了i∈Iprei。Pi1−µ→PJ对于每个k∈Iµ(par) P1−→PJµ隐含P1|P2−→ PJ|P2(同步) P1−→ PJ1 P2−→PJ2 隐含P1|P2 −τ→PJ |PJ2(com)Pa−I I→?XIPJ和Pa−I I→!YIIPJ隐含P|P−τ→PJ[PJ[X]/Y](res)P−μ→PJ蕴涵P\a−μ→PJ\a,如果a/∈ch(μ),o∈{I,II}o o(rep) P|!P−µ→PJ意味着!P−µ→PJ(app) P[P/X]−μ→PJ蕴含(λX. P)P−µ→PJ表3高阶结构公理和规则。(par)、(sync)和(com)的对称对应物未示出。奇?VarI=def{aII?XI:aII∈ChII且XI∈VarI}ChII!VarII=def{aII!YII:aII∈ChII且YII∈VarII}表4动作类和它们的典型变量以及动作上的ch操作o ∈ {I,II}。变量和ch()o-算子的定义假定无声作用τ不包含在ChI和ChII中。2.3上下文互模拟为了引入上下文互模拟的概念,需要以下条件a我a我122阿尔达穆斯56RR× ∪×≈表示为=. 顺便说一句,τ є• −→的自反传递闭包记为=。 此外,委员会认为,µµµ=和−→关系式µє不被定义为=−→=,因为从p后退的子部分开始的SOS是不对称的具体地说,源项总是过程,因为它们没有自由变量;另一方面,输入和输出转换的剩余项一般都有自由变量。这种情况在高阶过程的世界中是典型的[17]例如)。• τ=defα,α=defα•广义置换是从变量集到变量集的映射,没有自由变量的项,给定一• 设T是项,σ是基代换。然后将T的每个自由变量同时代入其在σ下的像的结果记为Tσ。•假设R是一个没有自由变量的二元关系。 那么它的openextensiontoterms(withorwithoutfreevariables),RisgivenbyyPR<$Q如果和O<$如果PσRQσ对于每个基替换σ。我们可以要求R是序相关的,在这个意义上,R是并集(TI(Var)TI(Var))(TII(Var)TII(Var))的子集。然而,从技术上讲,这个附加条件是不必要的。• 没有自由变量的一阶项的集合由于整个机制,然后,下面的定义是值得注意的简洁。它看起来几乎像弱互模拟的然而,与之不同的是匹配条件,因为它涉及开放扩展特别是,如果µ是一个输出动作,则必须针对所有输入上下文比较PJ和QJ这方面可以被视为语境互模拟的本质。定义2.1TI上的二元关系是上下文模拟,如果P Q意味着:当verP−µ→PJ时,则对于某些QJ,Q=µQJ且PJRQJ。如果R和R−1都是这样的模拟,那么R是上下文bi模拟。所有子双模拟的并集由上下文互相似性表示。应该注意的是,作为所有上下文互模拟的并集,CSCt此外,Ct可以被证明是一个等价和一个同余[17,4]。也应该注意到,定义2.1坚持所谓的引入上下文互模拟的后期风格也有早期风格,阿尔达穆斯57RR≈−→(Y−→(YP 则对于某个Q,Q=II1B12两者是等价的[17]。2.4正态互模拟为了结束本节,我们回顾一下正常互模拟的概念 为此,我们需要正式引入触发器和复制器。触发器被定义为一个形式为s I的过程。Nil,其中sI是主语,Nil是不作为的常数,它被理解为空和;复制因子被定义为λXI形式的抽象。(!sI.XI)。 此类构建体分别由Trs或Reps表示,将sI称为触发器的主题,或者复制者正规互模拟的思想包括大大简化输入和输出动作的匹配条件。代替相对于所有输入或输入上下文分别比较残差,它们仅相对于作为输入的一个触发器或作为输入上下文的一个复制器进行比较定义2.2TI上的二元关系是正规互模拟,如果P Q意味着:i. WheneverP−µ→IJjµ^IQJ和PJR QJ。ii. Whene verPa−I I→?那么对于some,Q,J和some,bBIf ∈fchI(PJ,QJ),二级?XIJ J JQ=Q和P[TrbI/XI]RQ[TrbI/XI]。iii. Whene verPa−I I→!那么对于someQJ和somebBIf ∈fchI(PJ,QJ),a二等!YIIJ J JQ=RQ和P[RepbI/YII]RQ[RepbI/YII]。如果R和R−1都是这样的模拟,那么R是一个正常的双模拟。所有这样的互模拟的并集用Nr表示;我们称之为正常的互相似性。其特征如下(cf.[17]):定理2.3(Sangiorgi)3高阶过程的新SOS在上一节中,我们回顾了具有静态作用域的高阶流程的经典SOS可能是什么这个SOS被称为替代SOS。初步说明,如果触发器或复制器的主体是受限通道,则其连接作为替代SOS的第一个近似值,可以考虑重新-将公理置于!P1.P2a二等!YIIII(1)|P2-通过一个!P. Pa二等!YII黄树⟩|代表(P)\b |P,我2IIB我阿尔达穆斯58在0010其中bI是来自ChI的新鲜物。这一措施已经具有减少高阶触发通信的效果他们然而,如果想要描述上下文互模拟,采用这个公理来支持(为了解决这个问题,进程传递被完全废除SOS通过将触发器的创建移动到输入公理并用连接规则取代通信规则来做到这一点,可以预见的是,连接规则除了连接触发器和复制器之外什么也不做此外,所有新创建但尚未连接的触发器和复制器的主题都是标准化的。每当需要这样一个主语时,那么所讨论的过程项中包含的每个自然数都加1,取0。只要应用连接规则,就会发生相反的操作。我们称这些操作为移位和非移位。定义3.1项T的移位和不移位如下:将T中出现的每个n或n分别替换为n+ 1或n+1;用n−1或n−1分别替换T中出现的每个n或n作为一个附加条件,只能应用于T,如果它既不包含0也不包含z。我们继续讨论构成替代SOS核心的结构性公理和规则该组包括用于高阶输入(in-At)和输出(out-At)的公理用于高阶交织的规则(in-At)这条公理指出,输入前缀是通过移动接收上下文并将触发器Tr0替换为过程变量来执行的。换句话说,通过一个II的过程的输入被解释为抢占式的触发器Tr0的输入。比如我们有是吗?X. b?Y.(X)|Y)−a→?b?Y. (Tr|Y)−b→?在Tr 1|Tr 0。(out-At)这个公理指出,输出前缀是通过移动发送的进程,将复制器Rep0应用于结果,移动残差并将两者并行放置来执行的比如我们有一个!(c. 无)。b!(d. 无)−a→!代表团c. 无|b!(d.无)−b→!代表团c. 无|Rep(d.无),aII?XI. P−→At((P))[Tr0/XI]二级?aII!P1. P2−→AtRe p0<$(P1)< $ |(P2)a二等!在在阿尔达穆斯59P1−→二级?在 P P−→Ja二等!12名P2JP1|P2−→At(PJ1 [bI/0] |PJ2 [bI/0])\bIτ.Σ一个!是吗?/∈一个!是吗?τb?1在0e1e使用((par2-At)该规则指出,作为一个例子,人们可以考虑如果将前面两个例子中的过程并行放置会发生(1)是吗?X. b?Y. (X)|Y)的|一个!(c. 无)。b!(d. 无)−→在a?X. b?Y. (X)|Y)的|(重复0次)无|b!(d.无))−→Atb?Y. (Tr0|Y)的|(关于第1页)无 |b!(d. 无))第二个转换是有趣的,因为它的推理涉及子过程Rep 0 c的移位。无|b!(d.无)。(con-At)对于b1fchI(PJ1,PJ2).该规则规定了触发器和由互补输入和输出动作创建的复制器的连接方式:它们的主体0被一个新的一阶通道b I替换,该通道对触发器和复制器是私有的未移动。作为一个例子,可以考虑(1)的以下扩展是吗?X. b?Y. (X)|Y)的|一个!(c. 无)。b!(d. 无)−→在a?X. b?Y. (X)|Y)的|(重复0次)无|b!(d. 无))−→Atb?Y. (Tr0|Y)的|(关于第1页)无 |b!(d. 无))−→。(三)|Tr)|(Rep. 无|报告。Nil)\e,其中e是新鲜的。第三个转变是有趣的,因为它是从b?Y.(Tr0| Y)−→ 在Tr1 |Tr0和代表团c. 无 |b!(d.无)−b→!在Rep200c。无|重复1次。没有。这句话结束了对另一种SOS的具体方面的描述所有其他公理和规则保持P1−→αⅡ在P1 JP1|P2−→αⅡ在 P|J1(P)2阿尔达穆斯60不变。完整的数据集见表5。阿尔达穆斯61我−→µµ−→−→a我a我τ−→−→µ1 2我在我1 2在我0我01012(P1 [bI/0] |P2[bI/0])\bI对于bI/∈fchI(P1,P2)(res-At)P−→PJ蕴涵P\ao−→.在µ(pre- A t)α。P−α→I在P(in–At)?X. Pa−II→?XI((P))[Tr/X],其中Tr =0的情况。无(out–At)!P.Pa二等!YII销售代表(P)|(P),其中Rep0 =(def)(!z.(XI)[XI](cchoice-At )π k. Pk−→AtPJk蕴涵<$i∈Iπ岛PiµI−→At PJK对于每个k∈I(par1在PJ1 隐含P1| P2−→ 在PJ1 |P2(par2–At)αⅡ在PJ1 隐含P1|P2αⅡ在PJ1 | (P2)(sync在PJ1 蕴含P2−→在Pj2和p1|P2 −→At PJ1 |PJ2(con–At)二级?XIPJ和Pa二等!YIIPJ意味着1点12 分J Jµ在At2J J在如果ao/∈cho(μ),o∈ {I,II}µ(rep-At) P|!P−→在PJ处且!P−→ PJ(appl- A t)P [ P / X ] − μ → P j蕴含(λ X. P)P−µ→PJ表5替代结构公理和规则。未示出(par 1-At)、(par 2-At)、(sync-At)和(con-At)的对称对应物 请注意,输入和输出动作被赋予了变量,就像第2节中SOS上下文中的输入和输出如果简单地省略掉这个禀赋,公理和规则也会同样有效。然而,跟踪这些变量是必要的,以证明上下文互模拟和延迟互模拟的替代语义是等价的。 通过对两种语义使用相同的动作格式,这种必要性以最简单的方式得到了考虑。4晚期语境互模拟上一节介绍了我们所谓的具有静态作用域的高阶过程的替代SOS然后,本节的主要部分概述了如何证明这一特征。4.1定理首先,根据[9]的延迟互模拟的概念被实例化到替代转换语义。这一步是可能的,因为语义学可以有意义地被认为是一个标记的转换系统,也是在[9]µIII在(def)II2在PJO,阿尔达穆斯62的意义上。我们称之为等价替代双相似性。作为阿尔达穆斯63RR在≈−→我/∈在对于p类,=ππ表示=πτ的恢复和过渡闭包At;µєµ=At表示=At和−→At的关系积。定义4.1如果P Q意味着:当verP−µ→PJ时,则对于某些QJ,Q=µQJ且PJRQJ。在如果R和R−1都是这样的模拟,则R是替代的bi模拟。我们用Δ t表示所有交替互模拟的并集,称之为交替互模拟互相似性.可以预见的是,替代互相似性本身就是一种替代互模拟。此外,以下引理是证明特征定理的先决条件:引理4.2交替双相似是一个同余。这个性质可以直接证明,通过调整和扩展所谓的Howe方法(参见[4]的证明和[11]的方法的原始介绍)。正规互模拟的同余性质没有任何已知的直接证明(参见。[17])因此,引理4.2的直接证明的存在可能是相当令人惊讶的。然而,必须记住,正常互模拟是在高阶过程的标准SOS上定义的同时,互模拟博弈受到很大的限制,这种情况似乎是正常互模拟的直接同余证明如此另一种SOS不涉及项替换;这一事实使得引理4.2的直接证明成为可能。正常互模拟和交替互模拟之间的另一个重要区别是,正常互模拟游戏涉及选择相对于残差而言是新鲜。这方面可能看起来像是一个小的技术问题,但事实上,一旦完全抽象的指称语义等问题变得有趣,它就会成为一个重要的问题。具体地说,天真的想法是在渲染的基础上获得“正常”的从Pa−I I→的每一次转变?如果P − a → I,则XIPj?PJ[TrbI /XI],并根据把形式Pa−II→的每一个转变都呈现出来!YIIPJ为Pa二等!PJ[Repb /YII],其中bIfchI(PJ)在这两种情况下。 随后的语义不会完全抽象,因为双相似过程不一定具有相同的免费频道类似的情况可以在π这也是为什么π演算的完全抽象指称模型需要更长的时间来开发,并且与CCS类过程的模型相当不同的原因之一另一种行为语义则回避了这个问题。在它的基础上,就有可能解释高阶过程,使它们尽可能地还原为一阶实体(参见第二章)[4]第五节)。阿尔达穆斯64为了结束这一小节,剩下的就是根据替代双相似性来陈述上下文的特征定理4.3ΔCt=ΔAt4.2定理证明大纲4.2.1先决条件输出电阻定理4.3的证明的第一个先决条件是明确哪些项可以作为第2节中SOS生成的跃迁的输出残差出现我们用O表示单个输出残差,用OR(Y)表示某个变量Y上的整个输出残差集。该集合由下式给出:O::= YP1|P2|O|P|P|O|O\a o,对于P1,P2,P∈ T I和o∈ {I,II}。下面的引理验证了这个定义:第1部分指出,每个残差-一个a!Y是OR(Y)的元素;第2部分指出OR(Y)的每个元素,其中Y是任意的引理4.4(i) P−a→!YPJ蕴涵PJ∈OR(Y)一个!Y(ii) 对于每个a∈ChII,O∈OR(Y)蕴涵P−→O,其中P是过程这是由替换子项YP1|O的P2由a!P1. P2.分解因式分解的思想,这是由于桑吉奥尔基[17],是最具决定性的在这里,它可以被看作是基本上说明Q可以从形式P[Q/X]的每个上下文中分解出来,直到上下文互模拟,使用触发器和复制器。如果上下文互模拟被交替互模拟所取代,该定理也可以被证明。在这种能力下,我们称之为选择因子分解定理(AFT)。定理4.5(因式分解)设R ∈ {<$Ct,<$At}.1. 设λX. P∈ T Ⅱ和Q∈ T Ⅰ。然后P [Q/X] R。P[Tra/X]|当a∈C hI\f c hI(P,Q)时,Re p a <$Q <$<$\ a.2. 设Y∈VarII,O∈ OR(Y),X∈VarI,P∈ T I(X)是{ X }中的一阶自由变量项集. 然后O[λX. [P/Y] R.O[Re pa/Y]|当a∈ChI\f c hI(P,Q)时,P [Tr a / X ] ∈\a.阿尔达穆斯65µ⇒≈在P那么,对于某个Q,Q=双向模拟-最多另一个技术性更强的先决条件是证明双相似性的因为这个方法是众所周知的,所以它需要马上陈述相关的定义和引理对本文件的框架只有一些小的定义4.6在TI上的二元关系R是一个上下文模拟,如果PRQ意味着:当verP−μ→PJ时,则对于某些QJ,Q=μ∈QJ且PJ(R ∈),J。CT如果R和R−1都是这样的模拟,那么R是一个直到XCt的上下文bi模拟。引理4.7对于T I上的每一个二元关系R,它是一个上下文互模拟,直到ΔCt,我们有RΔCt。定义4.8TI上的二元关系R是一种替代模拟,如果PRQ意味着:当P−→JjQJ和PJRQJ.如果R和R−1都是这样的模拟,则R是直到Δt的替代bi模拟。引理4.9对于TI上的每一个二元关系R,它是一个可替换的双模拟,直到Δt,我们有RΔ t。4.2.2业务通信引理4.9总结了先决条件。转向证明的主要部分,我们首先展示了标准和替代转换语义的对应结果,如下所示:• 每个可见的标准过渡都可以转换为具有相同标签的替代过渡,反之亦然。• – For every invisible standard transition, there is an invisible- 相反,对于每个不可见的替代转换,存在不可见的标准转换,使得残差是上下文双相似的。利用这个结果和上下文和替代互模拟的因式分解定理,我们证明了,后来,替代互模拟是一个上下文互模拟到Δt,反之,上下文互模拟是一个替代互模拟到Δ t。等价定理是它的直接结果。作为对应引理的技术预备,需要引入形式[X/Tr0]和形式[Y/Rep0]的替换,其中在在阿尔达穆斯66∈∈≈ ≈拉斯、、在在X变量I和Y变量II。假设调用了α和Y不会被意外捕获。引理4.101.I. P−α→Iii. P−a?→Xiii. P−a→!YPJ蕴涵P−α→IPJ蕴涵P−a?→XPJ意味着P-a→!YPJ((PJ))[Tr0/X]((PJ))[Rep/Y]在0τJτJiv. P−→P意味着,对于某些P,P−→AtP和P在P2.I. P−α→Iii. P−a?→XPJ蕴涵P−α→IPJ蕴涵P−a?→XPJ(PJ[X/Tr0])iii. P−a→!YPJ意味着P−a→!Y(PJ[Y/Rep])在0τJτJiv. P−→AtP意味着,对于某些P,P−→P和PP2P证据(思想)通过过渡归纳。 详情见[4]。✷请注意,将具有高阶标签的标准转换转换相反,变换具有高阶标签的替代转变此外,无声转换的对应性比其他情况下弱,因为这种转换可能隐藏通信或连接步骤。具体地说,无声步骤的对应需要使用适当的因式分解定理。这种情况下,允许一个相关的通信连接只有到bissimilarity。4.2.3第一千一百零六章结束证明证据(定理4.3,Ct= At)“":为了证明这个包含,我们证明At是直到Ct的模拟。那么,根据对称性,到1000吨。由引理4.7得出的结论是:所以假设P<$AtQ和P−→PJ。 我们只考虑μ=a的情况!Y因为μ=αI,μ=a?X和μ=τ更容易或非常相似。在在这种情况下,由Lemma4.10(1,iii),P−a→!YP,其中P=((PJ))[Rep/Y]和nd0一个!Y此外,通过P<$AtQ,Q =<$Q,其中对于某个Q,P<$AtQ。其余步骤如下:1. 我们构造了一个转换Q一个!YQJ使得(Q[Y/Rep])QJ.(下图中最右边的箭头0 Ct2. 我们在这里表示PJ(AtCt)<$QJ,t,其中包括的pr o。(下图中的虚线P,,a!Y≈At,Q一个!,Y,一个!YJ,,,,在......As,,t,一个!YzCP,J,((PJ))[Rep0/Y]Δt Q,(Q[Y/Re p0])(单位:μCt)、、、、在在在在阿尔达穆斯67在在1在在1LττLl+1∈0CT在1. 对于这一步,我们要区分Q是否=a?!YQ实际上是形式Q−a→的跃迁!YQ或一个真正的weak一个他的形式Q−τ→Q−τ→.. . -τ→ Q-a→!YQ,其中k≥1。在第一种情况下,理想的结论直接由引理4.10(2,iii)得出є在第二部分中,我们首先证明存在一个QJl,使得Q=<$QJl,对于每个l ∈ {1,.,k}。我们通过对l的归纳来做到这一点:l=1:由引理4.10(2,vi)直接得出。注意,Q=QJ是,因此,τJ1实际上是Q−→Q1形式的强跃迁。l→l+1:这里存在一个QJ,使得Q=l→l+1,且QL l生物量QJL. 我们有Ql−→At Ql+1,由此引理4.10(2,vi)暗示存在l+1 所以Ql−→Ql+1 和Ql+1 生物量l+1. 然后,因为是一互模拟,存在一个QJl+1所以QJ=QJl+1 和Q生物量QJl+1。这一事实意味着Q=QJl+1 与Q1+ 1生物量QJl+1。总之,存在一个QJk所以Q=QJKQk生物量QJk。获得aQJ,所以Q一个!YQJ和(Q[Y/Rep])QJ基本上是重复上述诱导步骤的问题,这次呼吁引理4.10(2,iii).下图描述了k≥3时的这个参数QτQτQτQQ,A!YQ,,在1,两点,3时k ,在、、、、、生物量、、生物量生物量、、、、、,,,,z,z...一个!Y,zτ, 、、、、、、Q2生物量年q3生物量QK生物量(Q[Y/Rep0])细胞计数CtzQJ1zQJ2zQJ3QJka!YzQJ2. 这一步包括关闭互模拟直到λCt,或者换句话说,满足证明义务PJ [λX]。阿QQττCT阿尔达穆斯68.Σ≈≈≈R/Y] λAtλCtQJ [λX. R/Y],对于每个λX。II.我们这样做的主要工具是AFT和(普通)分解定理要应用这些技术,我们需要以下技术先决条件:a. 设b是刚从ChI出来的。b. 我们有PJ [Repb/Y] =((PJ))[Rep0/Y][b/0] ,并且如证明开始时所述,((PJ))[Rep0/Y]AtQ。因此,我们认为,PJ[Repb/Y]At(Q[b/0]),因为At由主题替换保留我是说。c. 通过替代SOS,0在Q中恰好出现一次, 即 在复制子因此,(Q[b/0])=阿尔达穆斯69.Σ≈ ≈ ⊆≈µ−→CT≈ ≈、、⊇⊇CT((Q[Y/Rep0]))[Repb/Y]。最后的推理如下:P [λX. R/Y]在(P [Rep b/Y] |R [Tr b/X])\b; AFT,使用(a)2014年10月20日,(Q [b/0])|R [Tr b/X])\b ;(b),引理4.2=((Q [Y/Rep0]))[Repb/Y] |R [Tr b/X]\b;(c)0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000(Q [Y/Rep0]))[λX. 因子分解定理[λX. R/Y];(1)“⊆”: The proof of this inclusion is largely complementary to that of theother原子 结论是,Ct At,则遵循对称性和引理4.9。所以假设P<$CtQ和P−→AtPJ。我们再一次只考虑的μ=a!Y,因为其他的更容易或非常相似。在这种情况下,根据引理4.10(2,iii),P一个!YP= P =(PJ [Y/Rep0]),进一步,一个!YPCtQ,Q = Q用P=Q换Q。 其余步骤类似于“证明”中的(1)和(2)1. 我们构造一个跃迁Q−a→!YQJ使得((Q))[Rep/Y]QJ.在(下图中最右边的箭头0At2. 我们证明PJAtCtQJ,从而得出证明结论。(下图中的虚线P,,,,,a,!Y生物量,Q一个!,Y,,一个!Y J在,z,,,,,,,s,一个!YATCZP,J,(PJ[Y/Rep0]) Q,((Q))[Rep0/Y])Δt,Q,J电子邮件第一步实际上是对““证明中第一步的完全补充,因此可以省略。至于第二步,这一步比证明““的第二具体地说,它不需要使用任何因子分解定理。要看到这一点,让我们注意以下先决条件:a. 通 过 替 代 SOS , 0 在 PJ 中 恰 好 出 现 一 次 , 即 在 复 制 器 的 因 此 ,(PJ[Y/Rep0])是完全定义的b. By(PJ[Y/Rep0])≠CtQ和存在的事实◦通过主体替换, 我们有(((PJ[Y/Rep0])[Rep0/Y]Ct((Q))[Rep0/Y]。......
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功