没有合适的资源?快使用搜索试试~ 我知道了~
简洁图与函数互模拟及其特性研究
理论计算机科学电子笔记100(2004)5-29www.elsevier.com/locate/entcs简明图与函数互模拟张玲奈梅亨大学计算机科学系P.O. Box 9010,6500 GL Nijmegen,TheNetherlands电子邮件:lcheung@cs.kun.nl杰西·休斯1埃因霍温技术大学哲学与伦理学系P.O. Box 513,5600 MB Eindhoven,TheNetherlands电子邮件:J. tm.tue.nl摘要我们调查的条件下,最少的互模拟存在关于集合包含。特别是,我们描述了一种自然的方式来删除冗余对从一个给定的互模拟。然后,我们介绍了简洁性的过程图,它的存在性的最小互模拟上述方法的特点。随后,我们考虑的类别的过程图和功能互模拟。这道菜有所有的余均衡器.二元积和余积可以通过一些进一步的假设来构造。此外,简洁图的全子范畴是过程图范畴的一个相对子范畴。关键词:函数互模拟,过程图,最小互模拟,简明图,乘积,商图1介绍在[1]中,Zena M. Ariola和Jan Willem Klop研究了项图和功能互模拟的结构特征。在那里,他们定义了一种秩序,[1]这项工作基本上是在第二作者受雇于奈梅亨大学计算机科学系时完成的1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2004.09.0036L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)≤34在项图集合上的关系≤FBG≤FBH惠函互模拟f:GH.证明了FB是一个偏序(直到图同构)。更令人惊讶的是,对于任何项图G,与G双相似的所有项图的集合形成关于≤FB的完全格。本文的研究开始于将这些结果推广到过程图的练习。我们遵循Ariola和Klop把函数双模拟作为我们的态射(尽管与他们不同,我们不研究相关的骨架范畴)。这就产生了P类。功能双模拟似乎是一个有趣的(如果非传统的)选择,因为它们与历史关系密切相关。事实上,同上的≤FB关系对应于[ 9 ]中≤ H的相反关系。事实上,直接应用Lynch和Vaandrager功能A B是“忘记”这个变量的结果以历史关系为出发点,我们考察了由此产生的范畴的基本特征。我们的目标是通过最小双模拟定义两个过程图的乘积(关于函数的双模拟),并通过Set(集合和函数的范畴由于过程图的结构比项图的结构更灵活,我们遇到了一些非平凡的困难,其中包括两个双相似过程图之间存在一个合适的最小互模拟这些图之间可能没有任何最小的互模拟(图1)。1),或者可能有非同构的最小互模拟(图。2)的情况。x,,0,,一个,一个,一个一个,一个...ss,,sa,,a,yrstzrstz,z,,z,,z,,1b2B bB bFig. 1.没有最小互模拟。我们解决这个问题,通过引入简洁图的概念(节。3)。如果G是简洁的,那么对于任意的双相似H(不需要简洁),可以构造G和H之间的最小互模拟。更确切地说,我们从G和H之间的任何互模拟R开始,并删除当R被给定[1]中描述的转移结构时BL. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)7·,·,一个,b,aB、、一个,b,aB、、·J,s t·z,zJ,s··········t·z,z·图二.非同构的最小互模拟:R(由虚线表示)和恒等关系。我们在第4节中致力于理解P的基本特征。 这个范畴有所有的余均衡器;因此,给定过程图G上的互模拟R,我们可以用R生成的最小等价关系构造商过程G/R。 我们利用这个事实来构造bisim的二进制余积- 图,只要其中一个图是简洁的。最后,我们转移到限制图的子范畴,并在类似的假设下构造二元积。在第五节中,我们证明了简洁图的满子范畴是P的相对子范畴。给定任意一个过程图G,存在一个这个运算可以看作是P(的骨架)上的一个闭包算子,简洁图的子范畴对应于由这个算子生成的闭包系统一般来说,相对子范畴是偏序集上闭包系统的范畴推广(参见[12]中的讨论)。第六节探讨了不简明的情况。我们表明,由佐恩但是,不保证唯一性。第七节简要论述了简明性检查的前景。我们提出了一个修改后的定义,称为明显的简洁性,它允许更有效的检查。2预赛过程图被标记为转换系统。(我们假设动作标签的字母表为A解释一下,进程图是一个三元组,G=<$G,eG:GP(G)A,根(G)<$G<$.集合G的元素是过程图的节点,记为s、t、u、v等。我们用a、b、c等表示动作(A的元素)。 然后写st∈eG(s)(a).t如果两个过程图G和H之间的互模拟是关系RG×H满足:、、、、一8L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)PP×(i) F或所有的s,sJ∈R,ifs→a且t∈ R,T ∈ J∈R。(ii) 对于所有的s,sJ∈R,ifsJ→a且t∈ R,T ∈ J∈R。tinGthereeisatJ∈Hsuchth atsJ→atJtJinHthereeisat∈Gsuchth ats→at(iii) 对任意r∈根(G),存在RJ∈根(H)使得<$r,RJ <$∈R.(iv) 对任意的RJ∈根(H),存在一个r∈根(G)使得r∈ R,RJ∈R.我们说G和H是双相似的,只是为了防止它们之间存在互模拟。感兴趣的读者可以参考[5],了解包括双相似性在内的各种并发语义的介绍。过程图显然是函子FX=(X)A的余代数,以及指定根的额外结构。从这个角度看,互模拟与F-互模拟相同(在共代数意义上)满足(iii)和(iv)。注:人们可能会试图使用集合G的子集与箭头G2之间的同构来将过程图G表示为余代数G[eG,roots(G)] P(G)A×2,也就是说,作为函子FJX=(X)A2的余代数。 然而,我们对互模拟的定义与FJ-互模拟在共代数意义上是不同的后者要求(取代上文第㈢和㈣项)• 对于所有的s,t∈R,我们有s∈根(G)i ∈t∈根(H)。众所周知,互模拟关系在任意并下是封闭的。我们使用符号Participto表示所有互模拟的并集,即, 关于集合包含的最大互模拟。一个互模拟R被称为最小的,如果没有真子集R再次是一个互模拟。 如果它与某个函数f的图形重合,则称它是泛函的。 我们把f的图写成Φ(f)。 对于给定的集映射f:GH,我们有Φ(f)是一个函数互模拟i,f是一个F-同态(在余代数意义下),满足• f保留根,即,若r∈根(G),则f(r)∈根(H);• fTroots(G):roots(G)roots(H)是满射的,即,对任意RJ∈根(H),存在r∈根(G)使得f(r)= RJ.当Φ(f)是一个泛函互模拟时,我们也称f为泛函互模拟.L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)9pp2.1路径和可达性字母pq等等,用于表示过程图中的路径。 我们写s~t表示注意路径和迹之间的区别:路径p有迹σ,如果σ是p中边的动作标签序列(以适当的顺序)。过程图的节点上的任何关系都会以自然的方式产生路径上的关系:定义2.1设R是过程图G和H之间的任意关系。设p = s0a1s1. s n−1a n s n且q =t0a1t1. t n−1和n t n分别是G和H中的两条路。则p和q称为R相关的,如果对所有0≤i≤n,si,ti∈R.请注意,与R相关的路径必须具有相同的长度和迹线.使用这个诱导关系,我们观察到互模拟可以用路径(而不是单个步骤)来定义。引理2.2设R是过程图G和H之间的关系,使得G的每个根与H的某个根相关,反之亦然。则R是互模拟当且仅当,对所有的s,t ∈R且s~使得p和q与R相关,反之亦然。sJ,the reisspatht~qtJ证据 “如果”部分是微不足道的,因为采取一个单一的步骤作为一个1. 逆命题可以通过对p的长度进行归纳而容易地证明。Q以下访问路径的定义改编自[1]。在文献中,它们也被称为运行或执行。定义2.3设s是G中的一个节点。 G中的一条路径p称为访问路径如果r~s,其中r是G的根. G的访问路径集合记为AccPath(G)。如果一个节点s有一条访问路径,则称它是可达的。令reach(G)表示G中可达节点的集合(具有从G继承的变迁)。在这里,我们陈述一些关于函数互模拟和最小互模拟的基本事实引理2.4设f:GH是泛函互模拟。• 如果H = reach(H),则f是满射的。• 如果G = reach(G),则Φ(f)是最小互模拟。引理2.5设R是G与H之间的极小互模拟。则有s,t∈R当且仅当存在s的R相关访问路径p和qp10L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)J⟨⟩P⟨⟩t,分别。证据定义RJ为满足该引理陈述中的条件的对s,t∈R的集合。利用R的极小性,证明了R也是一个互模拟。我们省略细节。Q推论2.6若R是极小互模拟且s,t在R中,则s在G中可达且t在H中可达2.2互模拟上的过渡结构下面是互模拟的一个众所周知的特征。定理2.7设G和H是过程图,R<$G×H。 则R是互模拟,如果在R上存在过渡结构(即, 的函数eR:R(R)A和子集根(R)<$R)使得投影π1:RG和π2:RH是泛函互模拟。注意,如果R本身是泛函的,那么π1是一个双射。在这种情况下,R同构于它的定义域。引理2.8设R是G和H之间的任何互模拟,并在R上固定一个过渡结构,使投影函数互模拟,如定理2.7所示。那么reach(R)又是G和H之间的互模拟。证据 投影π1:reach(R)G和π2:reach(R)H是泛函互模拟。应用定理2.7。Q定理2.7表明,对于任何互模拟,都存在一个使投影同态的过渡结构.我们对这里明确定义的最大的这种结构定义2.9设R是G和H之间的任何互模拟。定义R上的最大标记转移系统如下:(i)r1,r2是R的根当且仅当r1是G的根,r2是H;(ii) s,t如果s→a,则sJ,tj和在G中的sJ和t→atJ在H中。下一个定理指出R上的最大LTS满足定理2.7的条件。(This结果也在[1]中提到。)这是例行的验证,这实际上是最大的这种结构。在R是泛函的特殊情况下,最大LTS是使两个投影泛函互模拟的唯一LTS。L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)11⟨ ⟩ ∈⟨⟩Jt2定理2.10设R是G与H之间的任意互模拟。投影π1:RG和π2:RH是关于R上最大LTS的泛函互模拟.此后,除非另有说明,否则我们将始终对互模拟R施加最大LTS。我们应该强调这个定义与两个过渡系统的同步产物之间的区别。[3]):每对图G和H之间的同步乘积是唯一确定的(不一定是双相似的),而G和H之间的每个互模拟R(必然是双相似的)产生自己的最大LTS。引理2.11设R是G和H之间的任何互模拟。 则s,t到达(R)当且仅当分别存在s和t的R相关访问路径p和q。结合引理2.5,我们可以看到R是一个极小互模拟,意味着R=reach(R)。如果R不是最小的,那么有可能(但不是必需的)有不可达的对。例如,可以用所有对s、t安全地增加互模拟R,使得s和t是终止节点(即,那些没有向外的边缘)。将得到的互模拟称为RJ。取决于s和t的历史,对s,t可能是可达的,也可能是不可达的。inR.3简明图表简洁性是进程图分支结构的一个条件。正如我们将在定理3.8中看到的,简洁性限制了分支的可伸缩性,刚好足以保证在引理2.8的构造下存在最小互模拟。这种最小互模拟在随后的范畴发展中是至关重要的。定义3.1称过程图G是简洁的,如果G不包含不同但双相似的根,并且对于reach(G)中的所有s,t1,t2a a(s→t1和s→t2和t1参与2)<$t1= t2。图(1)说明了禁止的情况。这里的直觉是,as,, a(一)cc,t参与zz112L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)⟨ ⟩ ∈1112121在实践中,这种情况可能以以下方式出现:程序执行布尔测试它们是双相似的状态)。在[2]中提出了一种抑制这种无用布尔测试的算法。简洁性比确定性弱得多,因为我们仍然可以从同一个节点采取两个不同的步骤,只要目标节点不是双相似的。还要注意,为了使图简洁,没有必要识别所有的双相似节点。换句话说,通过简洁性,我们可以有不同但双相似的节点,只要这些节点通过参与相关的路径不可达。我们给出了简洁性的另一种表征。它采取AccPath(G)上的证明原则的形式:“参与相关”的关系 这个证明原理对AccPath(G)i成立,并且G是简洁的.这类似于余代数的余归纳:余代数C上的关系Participant和恒等式一致,i∈C是最终余代数的子余代数引理3.2进程图G是简洁的当且仅当,对于所有访问路径,p和q在G中,我们有p与q i参与相关,且p = q。请注意,函数互模拟可以被视为识别域中某些双相似节点的操作,因此它永远不会创建非简洁的情况。也就是说,功能互模拟保持简洁性。引理3.3设f:GH是泛函互模拟。如果G是简洁的,那么H也是。证据 设r1和r2是H的双相似根. 由于Φ(f)是互模拟,我们在r根(G)中,当f(r1,J)=r1,f(r2,j)= r2时,我们可以得到r1,j和r2,j. 亨斯R1J和R2J是双相似的。 通过对G的简化,r1J=r2J,因此r1=r2。现在我们有一个posee(inreach(H))s→atands→atwithtandt2 1 2双相似的 根据引理2.4,所有这些节点都在f的范围内。选择SJ∈G使得f(SJ)=s. 由于Φ(f)是互模拟,我们可以选择tJ1withsJ→atJ且f(tJ)=t。 类似于T。Sincet和tarebissimilar,所以是TJ1和TJ2。根据G的简洁性,我们得出tj1=tj2,因此t1=t2.Q下面的引理将被用来构建第二节中的余积四、引理3.4设G、H和S是过程图,S是简洁的。 设g:GS和h:HS是泛函互模拟,R<$G×H是一个 最小互模拟则对所有的s,t∈R,g(s)= h(t).证据设s,t,R为已知。 根据引理2.5,我们分别有s和t的R相关访问路径p和q.由于Φ(g)是泛函的,因此必须存在g(s)的访问路径l,使得l和p是Φ(g)-1相关的。类似地,L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)13。,t,、、、、∈⟨ ⟩ ∈ ⟨⟩,tJ是h(t)的访问路径lJ,使得q和lJ是Φ(h)相关的。 因此,l和lJ是Φ(h)<$R <$Φ(g)-1相关的;这里<$表示关系合成。通过S的简洁性,这意味着g(s)=h(t)。·,t·,t·,t·,t,t,t.,t、G,t,t.,t.s,,t,t,t.,t,t、 、、(个)Φ(g)RtΦ(h)h(t)Q引理3.4的另一个证明是使用定理3.8。我们可以把Φ(h)<$R<$Φ(g)-1看作是到达(S)上的关系。它3.1最小互模拟第一步,我们观察到以下普适性质。定理3.5设R是G与H之间的任意互模拟。假设G或H是简洁的。设S是任意具有函数互模拟g:SG和h:SH的过程图.然后g和h对到达(S)的限制因子(必须唯一)通过到达(R),如Diag所示。(二)、reach(R)(2)π1,,、、、G,π2,,z,,Hg†到达 、、,h,†(S)(S)到达(S)达到证据 不失一般性,我们假设G是简洁的。让我们达到(S)。选择s的访问路径p。 根据引理2.2和Φ(h)是互模拟的事实,在H中必须存在一条访问路径q,使得p和q是Φ(h)相关的。类似地,在G中存在访问路径l,使得l和p是Φ(g)-1相关的。另一方面,由于R是互模拟,因此必须存在访问路径LJ,使得LJ和q是R相关的。 因此l和lJ是(R-1<$Φ(h)<$Φ(g)-1)相关的。通过引理3.2,我们得到g(s)=end(l)=end(lJ),因此g(s),h(s)=end(l),end(q)R。应用引理2.11得出g(s),h(s)可达的结论inR.Q正如我们将在定理4.8中看到的,映射reach(S)R实际上是一个函数互模拟。。-114L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)中文(简体)联系我们考虑示例性非简洁图G,如Diag. (一). 设R是恒等关系<$G。从G到它自身有两个函数互模拟:恒等函数g=idG和交换函数h将s映射到s,t1映射到t2,t2映射到t1。定理3.5的结论在这个例子中失败了,因为 g(t1),h(t1) =t1,t2R. 这表明,对于一对非-简洁的图,二进制产品不能以简单的方式使用任意的最小互模拟来构造下面是定理3.5的直接结果。推论3.6如果G是简洁的,并且H与G双相似,则reach(R)=对于G和H之间的任何互模拟R和S,reach(S)。推论3.6意味着到达(R)(对于任何R)包含在G和H之间的所有互模拟的相交中。结合引理2.8,这个交集必须正好是reach(R)。总之,我们有以下定理。定理3.7若G是简洁的,则对任意H与G的双相似和任意G与H之间的双模拟R,reach(R)是G与H之间的最小互模拟(关于集合包含).这给出了一个相当强的暗示,即简洁性在多大程度上限制了过程图的分支结构;即,基本上只有一种方法来构造简明图和任何其它双相似图之间的互模拟。考虑H与G重合且R是恒等关系<$G的特殊情况。然后定理3.7说,从G到它自身的每一个互模拟都必须包含到达(reach)。(注意reach(reach)(reach(reach)(reachG))是仅限于G的可达节点的reachG。当G不简洁时,这很容易失败:在(1)中,恒等关系不包括在交换关系{s,sn,t1,t2n,t2,t1n}中。此外,在同一个图G中,关系R:=<$Gt1,t2是互模拟,并且reach(R)=R;但显然R不是最小互模拟。因此,定理3.7以不同的方式失败。现在我们通过证明定理3.7的逆定理来加强定理3.7这是简洁的另一个特征。定理3.8设G是过程图. 以下是等价的:• G是简洁的;• 对于任何过程图H与G的互相似以及它们之间的互模拟R,reach(R)是G与H之间的最小互模拟。证据前向蕴涵是定理3.7。 相反,假设G不是简洁的。设ParticipG是从G到G的最大互模拟。我们主张L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)15212我们可以在reach(ParticipG)中找到t1,t2,使得t1不同于t2:(i) 如果G有不同的但双相似的根,则我们设t1,t2为一对这样的根.根据定义,这是ParticipG的根;因此它必须是可达的。一(ii) 否则,我们选择见证人s,t1和t2(在reach(G)中),使得s→t1,s→at,ndt和t是不同的,但不是双相似的。让我来帮你色葡萄 则pat1和pat2是参与者相关的访问路径。 根据引理2.11,在ParticleG中,t1,t2是可达的。现在来考虑互模拟问题。当然,t1,t 2,t 3,t 4,t 5,t 6,t 7,t 8,t9,t10。这意味着reach(ParticipeG)不是一个子集,因此不是从G到G的最小互模拟。Q在结束本节之前,我们提出以下问题:定理3.8中的最小互模拟R何时是函数互模拟?定义3.9我们说一个进程图H是一个森林,如果H中的每个节点只有一条访问路径(特别地,这意味着reach(H)=H。直观地,如果H中的t具有多于一个的访问路径,则可能需要互模拟R来将t与G中的多个节点相关联,因为H中的每个访问路径必须在G中具有R相关的对应物。因此,为了证明函数互模拟的存在性,我们要求reach(H)是一个森林。随之而来的必然结果是直接的。定理3.10假设G是简洁的,并且H与G是双相似的,此外,假设H中的每个节点最多有一条访问路径(即,reach(H)是一个森林)。则G和H之间的最小互模拟R(定理3.7)是从H到G的部分函数,total on reach(H)。证据设t∈reach(H)给定。则t必须与G中的某个节点相关(通过R)。设s1和s2是两个这样的节点。它表明s1=s2。通过对H的假设,存在t的唯一访问路径p。由于R是最小的,我们可以应用引理2.5,分别得到s1和s2的访问路径q1和q2此外,q1和q2是(R-1<$R)相关的。现在应用G的简洁性和引理3.2,我们可以得出s1=s2,因此R是从reach(H)到G的部分函数的图。Q推论3.11设G参与GJ,其中GJ是简洁的,H参与HJ,其中HJ是森林。则G参与Hi ≠有一个函数互模拟HJGJ。特别地,这适用于当H J是H的开折,并且GJ是G的标准简明图(在第5节中构造)时。16L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)≡-14进程图在本节中,我们定义了四个密切相关的过程图类别其中最基本的是过程图和功能互模拟的P类。范畴CP是P的由简洁过程图构成的全子范畴。如果reach(G)=G,则称过程图G为受限图.我们用RP表示受限过程图的全子范畴,用CRP表示简洁受限过程图的全子范畴。我们将在第5节中更详细地探讨这四个类别之间的关系。目前,我们表明,这些类别中的每一个继承coequalizers类别集。共均衡器将被用来构建copro管道(节。四、2)和P的最小值CP(第5节)。我们把二元产品的处理放在本节的最后,因为它要求我们在RP(的子类别)中工作。4.1余均衡器在本节中,我们考虑一种常见的范畴构造:余均衡器,它是范畴集上等价关系对等价项的标准推广。由于我们将在Set中显式地使用coequalizer的构造来表明我们的类别中有coequalizer,因此我们在这里回顾一下这个构造。设XFG Y是给定的(在集合中)。 定义一个关于Y的关系,=Φ(g)也就是说, y<$yJi <$存在一个x∈X使得f(x)=y和g(x)=yJ。 让我们 最小的等价关系包含那么,映射YYi是f和g的余均衡器。为了证明同样的构造在我们的设置中产生了一个coequalizer,我们依赖于以下内容引理4.1设G是一个进程图,R是G上的互模拟。设R是包含R的最小等价关系。那么,互模拟也是一种互模拟。L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)17≡K证据 为此,我们以通常的方式显式地构造了一个函数。也就是说,0=Rn+1==由于R-1和R-1也是互模拟,并且互模拟在联合下是封闭的,所以R-0是互模拟。互模拟在复合下是封闭的,因此每个双随机数n都是一个互模拟。再次,我们呼吁关闭工会下的结论,这是一个互模拟。Q定理4.2范畴P具有所有的余均衡器,并且这些余均衡器通过将图取到其节点集的遗忘函子保持。换句话说,健忘函子PSe不创建余均衡器。CP、RP和CRP类别也是如此。证据我们证明了过程图的范畴P的结果。对于其余的范畴,它表明将G取为G/的运算保持了限制性和简洁性。我们忽略那些简单的证明。F设HgG是函数互模拟。 定义最小和最小关系在上面的G。因为互模拟在复合下是封闭的,所以互模拟是一个互模拟,因此互模拟也是。我们通过以下方式将LTS结构强加于G/T:首先定义roots(G/G)={[r] |r∈roots(G)},其中[r]表示陪集(即,等价类)的R。我们定义一个过渡[s]→a[t]jinc,因为它是G中的s→atj的一个过渡。我是我是定义明确,因为互模拟是互模拟。此外,很容易看出商映射[−]:G G/在这个定义下是一个互模拟。假设k:GK是一个函数互模拟,使得下图的第一行可交换。我们必须证明存在唯一的功能互模拟,如虚线箭头所示,使三角形可交换。FHgG[−]K 、JG/2000显然,有必要且充分地证明,集函数G/GK定义为[s]<$→k(s)是一个函数互模拟。 这个函数的图形18L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)JJGHH是关系式Φ(k)<$Φ([−])-1,而hence是一个二进制数。Q给定一个G上的互模拟R和一个泛函互模拟f:GH,我们说f尊重R,如果只要sRt,我们有f(s)= f(t)。推论4.3设R是进程图G上的互模拟。有一个过程图G/R和一个函数互模拟q:GG/R,使得每个函数互模拟f:GH关于R个因子通过q唯一,如图所示。F、QG/R证据我们把R看作一个过程图,它有最大的LTS(第2节)。注意,f关于Ri,f等于投影RG。 另一方面,这些投影是泛函互模拟,因此我们可以应用定理4.2来获得它们的余均衡器q。设G/R是q的余域。因此,从G/R到H有一个独特的功能互模拟,使图可交换。π 1Rπ2GQG/RF 、Q注释4.4解释一下,G/R的构造如下。取R生成的等价关系为R的等价关系。则G/R的节点是G的陪集。 陪集是R的根,如果它包含G的某个根。对于G中的每个s,t,是一个转变[s]→a[t]it这里是一个转变s→atJ,对于sometjt。4.2二元余积现在我们转向双相似过程图的二元余积。我们通过首先取集合中的余积G+H来实现这一点(即,不交并)。在G+H上有一个明显的过程图结构,但所得到的图不是G和H在P(或其子范畴RP,CP,CRP)中的余积。相反,我们定义了G+H上的互模拟R,并证明了(G+H)/R(如推论4.3所示)满足上积的泛性质。为此,我们假设G和H中至少有一个是简洁的。让• root(G + H)=root(G)<$root(H);L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)19一G+Ha a• inG(s)→inG(t)当且仅当s→tinG;• 在H(s)→在H(t)中也是如此注意,G:GG+H和H:HG+H中的包含一般不是双模拟,因此G+H不能是G和H在P.考虑定理3.8给出的G和H之间的最小互模拟R.它可以以明显的方式被看作是关系RG+HonG +H也就是说,RG+H= Φ(inH)<$R(Φ(inG))-1,其中,inG和inH分别是G和HG+ H设R表示关系RG+H= RG+H(RG+H)-1.为了构造(G+H)/RG+H,需要证明RG+H是G+H上的双模拟.引理4.5设R是G和H之间的任何互模拟。那么R,如上定义,是G + H上的互模拟。我的律师。很明显,G+H的每一个根都与其自身有关。Supposes→aG+H和S,sj<$∈R. 我们考虑三种情况。不在则s∈G且sJ∈H且s,sJ∈R。 因为R是abisimulation,re是a tJ∈Hsuchth a tsJ→atJ,且tt,tJ <$∈R. 因此,<$t,tJ<$∈RG+H<$R且sJ→as,sJ<$∈(RG+H)-1:相似。tJ在G + H中。则s = SJ且t∈R.Q下面,我们将简化我们的符号,用R代替RG+H。Letκ1:G(G+H)/RG+HbecomposieeGG+H(G+H)/R,和κ2:H(G+H)/R是H的相似模。 下面的引理(没有证明)确定这些映射实际上是P中的态射。然后证明了在P中,K_(G + H)/R,K_1,K_2_k构成G和H的余积.引理4.6映射κ1和κ2是泛函互模拟。20L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)⟨⟩、、、、◦◦×定理4.7设G和H在P(RP,CP,CRP,resp.)是双向相似的。假设两个图都很简洁。则G和H的余积存在于P(RP,CP,CRP,resp.)中。证据我们首先证明了P的结果。设(G+H)/R,κ1,κ2如上所示。 设S是具有函数互模拟g:GS和h:HS的图.我们证明了存在一个(必然唯一的)映射k:(G+H)/RS使得下图可交换。(G+H)/Rκ1,,κ 2、、,κ,2、、G,k,Hg,J,,zS,,o,h设m:G + HS是唯一的集合映射,使得m在G=g中,在H=h中, 很容易检查m是否是函数互模拟。 我们将证明m尊重互模拟R。根据推论4.3,这给出了所需的唯一映射k:(G + H)/RS。我们尊重RG+H。 对于εs,t∈(RG+H)-1,该公式类似;对于εs,t∈RG+H , 该公 式 为 三 值 .由定义可知,S,t∈RG+H表示s∈G,t ∈H和S,t∈ R. 根据引理3.4,g(s)=h(t),即,m(s)=m(t)。我们已经完成了证明,这个结构产生一个余积,P.现在,假设G和H分别在RP(CP,CRP)中。然后,(G+H)/R也在RP(分别为CP、CRP)中。由于包含的完整性和忠实性,(G+H)/R是RP(CP,CRP,分别)的副产物Q这种余积结构可能会因不简洁而失败。再次考虑Diag中的图G。(1)设R为交换关系。然后,在(G+G)/R中,识别两个叶子节点。这不是余积,因为从(G+G)/R到G不存在泛函互模拟。4.3二进制乘积构造两个过程图的乘积的简单方法是从笛卡尔乘积G H开始,并试图定义一个过渡结构,使得投影是函数互模拟。很快,人们意识到这个计划是不可行的。如果投影π1和π2是函数互模拟,则s参与者s,t参与G中所有的s,t。显然,一般情况并非如此我们得出RP中的二进制积不应包含非双相似节点对的结论。自然地,互模拟关系成为产品的候选者。L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)21⟨⟩∈⟨⟩产品的情况与那些具有余均衡器和余产品的情况不同,即我们的构造仅适用于RP及其子类别CRP。定理4.8设G和H是限制过程图。设G是简洁的,H与G是双相似的.则RP中存在G和H的二进制乘积。证据 根据定理3.8,我们得到了G与H之间的最小互模拟R。根据定理2.10,投影π1和π2是泛函互模拟。我们将证明,πR,π1,π2π构成G和H的乘积。设S是任意受限进程图,g:SG和h:SH是函数互模拟.由定理3.5,我们可以定义m(s)=g(s),h(s),对于S中的每个可达s。因为S是有限制的,所以m是一个全函数。我们认为Φ(m)是一个互模拟。事实上,设r,rJ是R中的根。则r∈根(G),RJ∈根(H). 由于Φ(h)是一个互模拟,我们可以选择 RJJ∈根(S),使得h( RJJ)=RJ。注意g(rJJ)根(G)。 此外,g(rJJ)ParticirJJParticirJParticir. 通过G的简洁性,我们得出g(rJJ)=r;因此存在S的根rJJ,使得m(RJJ)= rg(RJJ),h(RJJ)= rg,rj= rg。证明Φ(m)满足第2节中的转移条件(i)和(ii),同样使用G的简洁性和R上的最大LTS的定义进行。m的幺正性来自于π1和π2在集Q在定理4.8的证明中,我们使用S=reach(S)的假设来建立m的全体。如果没有这个假设,g(s)可能在G中不可达,在这种情况下g(s),h(s)一定不在R中(由于R的极小性)。 换句话说,对于S中不可达的节点,m可能没有很好的定义。这就是只考虑受限图的原因。很容易检验两个简洁图之间的最小互模拟R是简洁图;因此定理4.8中的构造也适用于CRP。5分类比较在本节中,我们讨论了各种类别之间的关系:P(过程图),CP(简明过程图),RP(限制过程图)和CRP(简明,限制过程图)。我们的主要目的是表明,CP22L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)0nnn不n+1个∼∈−›→∼∼是P的一个相对子范畴。这给出了一个构造的规范方法,对于每个过程图G,一个双相似的简洁图H。这种构造应该被看作是偏序上闭包算子的类似物,但有一点需要注意:图H是通过取G的一个商而构造的,而不是通过扩大G。在这个任务之后,我们评论限制过程图的类别。我们将定义一个函子conc,它将一个过程图G带到G/G/G,其中G/G是使G/G/G简洁的最小互模拟。我们首先描述互模拟的互模拟。设G是一个过程图。 我们在G上定义一个关系G,如下所示。G=Participant(roots(G)×roots(G))Gn+1个={s,t}|v,u,au→as,v→at,uGvandsParticit}G=B.G.第二个条款说,在某种情况下,uGv(三)a asJ参与者J我们需要你的帮助。特别注意,sGt意味着s和t都是公里.我们省略下面引理的证明。它涉及到归纳法的结构。引理5.1对于每个过程图G,关系G是互模拟。过程图G/G是根据推论4.3构造的。对于每个G2、我们定义conc()= GG/G和η G是满射GG/G。正如我们将在引理5.3中看到的,conc(G)是简洁的。注意,G本质上是通过向conc(G)添加一个历史变量而获得的,conc(G)是它的“concisi-tion”。换句话说:conc(G)是通过“遗忘”G中的一个(虚构的)历史变量而构造的首先,我们证明conc是函子,η是自然数。引理5.2设f:GH是一个泛函互模拟。对于G中的每个s,t,如果s<$Gt,则f(s)<$Hf(t).因此,算子conc是函子的,而η是一个自然的变换IdPzconc.证据第一个陈述可以通过对BLOG定义的简单归纳来证明。∼L. Cheung,J. Hughes / Electronic Notes in Theoretical Computer Science 100(2004)23∼pnn+1个G0n+1个Cc∼对于第二种情形,我们必须为每个泛函互模拟f:GH定义一个泛函互模拟conc(f):G/GH/GH。 根据推论4.3,它足以表明,fηHHG HH/尊敬的乔治。这等价于本引理的第一个陈述:对所有s和t,s<$Gt蕴涵f(s)<$Hf(t)。从我们对conc(f)的定义中可以很容易地得出η的自然性Q引理5.3图G/G是简洁的。证据 若[r],[rJ]是G/G的根,且[r]Participate[rJ],则rParticipate[r]Participate[rJ]ParticiparJ因此r=GrJ,即, [r] = [rJ]。 我们必须证明,对于每一个可达的在G/nG中,如果f[s]→a[t]and nd[s]→a[tJ]and nd[t]参与[tJ],则n[t] =[tJ]。Itsuccess因此,对于任意一个在G中可实现的具有s→a的transitiont参与者J意味着t <$GtJ。t和s→atJ我们有设r~s已知,其中r∈根(G). 一个简单的归纳表明s<$Gs,其中n是p的长度。 因此,t<$GtJ,因此tgtJ.Q定理5.4 CP是P的一个相对子范畴。explanatory,functorconc:PCP是包含CP,CP的左伴随.
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebLogic集群配置与管理实战指南
- AIX5.3上安装Weblogic 9.2详细步骤
- 面向对象编程模拟试题详解与解析
- Flex+FMS2.0中文教程:开发流媒体应用的实践指南
- PID调节深入解析:从入门到精通
- 数字水印技术:保护版权的新防线
- 8位数码管显示24小时制数字电子钟程序设计
- Mhdd免费版详细使用教程:硬盘检测与坏道屏蔽
- 操作系统期末复习指南:进程、线程与系统调用详解
- Cognos8性能优化指南:软件参数与报表设计调优
- Cognos8开发入门:从Transformer到ReportStudio
- Cisco 6509交换机配置全面指南
- C#入门:XML基础教程与实例解析
- Matlab振动分析详解:从单自由度到6自由度模型
- Eclipse JDT中的ASTParser详解与核心类介绍
- Java程序员必备资源网站大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功