没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记175(2007)65-73www.elsevier.com/locate/entcs局部偶图与同余:两个猜想(延伸摘要)罗宾·米尔纳剑桥大学摘要在双图的背景下研究了连通性的概念。在模拟真实世界的系统时,一致性将是重要的,无论是自然的(如生物学)还是人工的(如普适计算)。本文使用的bigraphs中的名称有多个地方,这使得制定明确的替代lambda演算。本文报告了正在进行的工作,寻求条件的bigraphical反应系统,足以确保concilience;条件必须处理的方式,bigraphical赎回可以错综复杂地交织在一起。这些条件也应该由lambda演算来满足。在对这些问题进行讨论后,提出了两点建议保留字:双图,局部性,连通性,lambda演算。双图已经被用来在一个单一的框架内表示各种并发模型,这也提供了一个适用于所有模型的理论。当我们寻求对广泛的现实生活系统的信息理解时,我们不能指望我们目前的抽象过程演算(包括Petri网,移动环境,CSP和π演算)会出现。因此,当我们扩大我们的演算库时--也许是特定于某个应用(例如生物学或普适计算)--就需要统一理论。传记模型是这方面的一个实验。它不是一个具体的演算,而是一个定义和组合这种演算的框架要定义一个特定的双图反应系统(BRS),需要两个要素:它的签名定义它的控制(允许的节点类型),它的反应规则定义双图如何重新配置自己。该模型已经产生了一个理论的一些元素,特别是标签转换和行为一致性[6,4,5,7],这是适用于各种BRS。本练习涉及一个不同的主题。首先,在局部双图[8]中,我们引入了一种新的名称处理方法,允许它们具有多个局部性(一个例子如下)。Bundgaard和Hilde在bigraphs中也做了类似的工作-1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.07.03566R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)65brandt [3].第二,我们研究的概念concilience-即行动之间的独立性-在这种情况下,相信它会经常出现在应用程序中。人们只需要考虑建筑物内的行为建模:建筑物一端的活动在很大程度上独立于另一端的活动。这个摘要省略了一些细节,但应该是那些不熟悉双图的人可以访问的。它总结的工作,其目的如下:了解当地的bigraphs的活动如何可以相互联系,导致非concilience;代表λ-演算-concilience研究的经典设置-在当地的bigraphs;从而学习条件下,concilience可以保证在这个更广泛的设置。这项工作正在进行中;摘要以两个结论结尾。数学框架:我们在s-范畴中工作。它们不同于在“如果有一个p或t”中的范畴, |F|,一个有限的集合;如果|∩ | F|= ∅, a n d t h en|gf|为|G|∪ | F|.|. 如果两个f和g仅通过其支集之间的双射而不同,则fg是上等价支持对于一个偶图在另一个偶图中出现的概念例如,我们的猜想1依赖于对两个redex事件何时以及如何相互重叠的分析1局部双图局部偶图是s-范畴中的箭头,其对象是接口。 接口I = X = ΣX0,. ,Xm−1有宽度m,一个有限序数,并赋予每个位置i∈m一个名称的有限集合Xi。Xi不需要是不相交的;因此,例如,任何x∈X0<$X1都有对偶局部性。若J=Y是另一个宽度为n的界面,则局部偶图G:I→J有m个点和n个根(或区域)。每个区域包含一个无序树,其根是区域,其其他成员是节点或站点;后者必须是叶子。这些接口规定了每个站点和每个区域的名称分配;G的内部和外部名称分别是I和J的名称。支撑|G的是它的节点集;我们说F和G重叠,如果它们的支撑不相交。|of G is its set ofnodes; we say that F and G overlap if their supports are not disjoint.图1显示了一个具有三个站点(阴影部分)和两个根的局部偶图;树由嵌套表示每个节点可以具有端口,端口的数量取决于节点端口和内部名称的集合被划分为链接;链接要么是自由的(外部名称),要么是由绑定端口绑定的。该示例有两个空闲链路xJ和zJ,以及一个由最大节点上的端口绑定的链路。绑定端口显示为圆形,自由端口显示为项目符号。有一个作用域规则:如果一个链接是绑定的,那么它的内部名称和端口必须位于绑定它的节点内;如果一个链接是自由的,外部名称为x,那么x必须位于包含链接的任何内部名称或端口的每个区域中G:I→J与F:H→I的合成,记作G→F,很容易用图形来定义:将F的根插入G的位点,在相似的名称处连接链接,并省略名称。观察到,通过组合,不同区域中的节点可以被任意多个节点边界分隔开-同时仍然共享链接。R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)6567x0的z更新资源x0的X10101x′z′zX yXzFig. 1.局部偶图G:n {xy},{xz},{z} n → n {xJ},{xJzJ} nRRJ图二. 参数反应规则代理a:→I没有站点;是宽度为0的平凡接口。我们用小写字母代表代理人。2反应规则与λ演算我们感兴趣的参数(反应)规则,重新配置代理。这样的规则有一个redexR:H→K和一个reactumRJ:HJ→K,它们可能有不同的站点数m和MJ。规则的一个参数是一个代理a:HI,宽度为m。接口HI的宽度为m;它将两个接口H和I合并,每个接口的宽度为m,通过在每个位置取名称的并集。H表示要被R绑定的a的名称;I表示要通过R通过额外的自由链接导出的a的名称。图2显示了一个参数规则,其中R和RJ都有两个站点。所以它接受一个宽度为2的参数a=a0a1,因子a0和a1都是单位宽度。平行复合的π可以从s-范畴中的张量积导出;如果a和b的宽度为m和n,且支集不相交,那么在一个宽度为m + n的πbR和RJ中的位点被编号;在RJ的第j个位点写上赋值j:=i意味着反应应该在这里放置a的第i个因子的拷贝。因此,所示的规则将丢弃0并复制1,在RJ的每个位点放置一个拷贝。(We省略每个副本的名称是如何确定的细节我们可以将该规则视为renew节点从资源节点(通过共享链接z)获取其资源a1的新副本。由于R有两个区域,在包含redexR的出现的大型二图中,更新节点和资源节点可以相距任意远;因此该规则允许在一定距离处采取行动的可能性。现在让我们用通常的方法定义一个λ-演算Λsub这是一个版本x0的z资源x0的0:=X11:=0168R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)65X林Xappvarlam(x)appvarxX子Xdefsub(x)defx图三. 离子为大,其代数表示有明确的替代,但比阿巴迪等人[1]粗的步骤。这些术语M::=x| λxM|MN|M[x:= N]最后一项的结构应该读作“M,其中x表示N”;它不应该与{ N/x } M相混淆,M定义2.1(约简)Λsub中的约简规则如下:(λxM)NdM[x:=N]({x/y}M)[x:=N]d({N/y}M)[x:=N]其中M具有唯一的y的自由出现M[x:= N]d M,其中M没有x的自由出现。约简可以应用于一个项的任何子项因此,即使在显式替换中也允许进行在第二条规则中,{x/y}M区分x的一个特定的自由出现被N替换。这三个规则一起实现β-约简。 显式替换[x:=N]依次在x的每个自由出现处“以一定距离”作用我们现在转向ΛBIG,对应于Λsub的BRS。图3以图形和代数方式显示了它的签名有五种控制(节点的种类),显示为离子(基本双图);var-节点没有站点,app-节点有两个,其余的有一个。lam-和sub-nodes绑定一条链路;var-和def-nodes有一个端口。一个节点的形状并不重要,除了应用程序的形状-R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)6569X(x)X X±x(x)X X±x x XXX x XX节点表示其站点按从左到右的顺序排列。1请注意绑定名称是带括号的。为了从其占用者导出自由名称,对具有站点的离子进行泛化到lam(x)idZapp(idY|idZ)sub(x){\displaystyle {\frac{x}{\displaystyle}{\displaystyle}应用程序从第一个站点导出名称Y,从第二个站点导出名称Z这里出现了两个新的操作员。在这篇摘要中,我们没有正式定义运算符,而是通过例子来说明它们的含义。一个素数组合F|G类似于F<$G(并且可以从F <$G导出),但它将F和G的外部区域合并为一个。运算符的名字叫做extension。接口的扩展IIJ 给定G:I→J和ω:IJ→JJ(一个连线,即一个无节点的偶图),只要定义了接口扩展,就可以形成G<$ω:I<$IJ→J<$JJ;它具有与G相同的树结构,但是G的连接通过添加ω的连接来扩展。因此,idY|idZ,内部宽度为2,外部宽度为1,是app的合适扩展;它将内部名称集Y和Z的并集导出为外部名称。运营商ESTA,ESTA,|和《古兰经》,虽然部分,有一个丰富的代数理论。由上述离子构建的偶图中的自由名恰好对应于λ项中的自由变量因此λxx(xy)将转化为双图(lam(x)idy)(app(idx|idxy))(varx((app(idx)|idy))(varxvary)))。(Here诸如{xy}的集合已经被写成没有花括号。) 当然,这个符号不推荐用于发展λ-演算理论!- 但它的优点是,每个术语构造函数导出的自由名称是显式的。我们现在把Λsub翻译成<$ΛBIG。转换函数[M]]X由集合X索引,集合X必须包含M的所有自由变量。 因此,每一项M都有许多偶图像。这种技术被用来模拟异步π演算[4]。定义2.2(λ-项转化为双图)[[x]]X±xd=efvarX[[λxM]]Xd=ef(lamnumerid)[[M]][[MN]]Xd=ef(应用程序名称(id|[[M]][[N]])[[M[x:=N]Xd=ef(sub_id)([[M]]|((d efid)[[N]]))。我们将不完全讨论这个翻译。但值得注意的是,alpha-可转换的λ-项具有相等的图像;这是因为绑定名被省略了,1多站点控件可以在排序规则的帮助下从单站点控件定义。70R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)65app林0 X1X0:=01:=1子def01子def0:=0一CDR RJ一 app( lam(x))sub(x){\displaystyle\sub(x)}|def x)C varx定义变量xid defxDsub(x){\displaystylesub(x)}|defx)ID见图4。 参数化反应定则混合物. 现在我们准备给出BRS<$ ΛBIG的反应规则。定义2.3(动力学)大有三个反应规则:A(应用),C(复制)和D(丢弃)。它们在图4中以图形和代数方式示出。请注意,规则C的宽度为2。因此,在C中,“变量”x的出现这个规则利用了局部双图中名字的多个局部性;它类似于图2的规则。我们现在断言,在ΛBIG中的反应与在Λsub中的还原完全匹配:命题2.4(反应匹配还原)[[M]] XDG 如果和仅当MdMJ对于某个MJ使得[[MJ]] Xg.事实上,对于每一个由针对Λsub的规则进行的约化,都存在对应的针对ΛBIG的规则的匹配反应,反之亦然。在最近的草稿中,我们在这里的目的是不同的;我们使用的X0:=01:=0defX0vardefR. Milner/Electronic Notes in Theoretical Computer Science 175(2007)6571是传记72R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)65******g0g0g0J J Jg g g g g gg1g 1g 1一步强弱图五. 三个概念的连贯性表示来说明我们一般寻求的双图的一致性。3偶图的同余回想一下,对于任何给定的还原或反应关系式他们都说,如果g可以反应成为g0或g1,那么这两个反应物可以反过来反应,得到一个共同的结果。很明显,一步式的强与弱,众所周知,这些蕴涵一般都是严格的对BRS来说,最积极的结果将是完全保持强烈的这对经典λ-演算确实是正确的(丘奇-罗瑟定理),对Λ sub也是正确的(O然而,在双图中,我们一般不能期望这一点。相反,我们将寻找确保两个竞争反应gdg0和gdg1之间不干涉的条件;这样的条件可能取决于两个平移背后的反应规则,以及两个基团在g中重叠的程度(如果有的话)。此外,在这种情况下,一般更容易建立弱连续性。如果我们成功地证明了弱连续性在某些反应规则下对某一类主体总是成立,并且如果这一类主体本身被反应所保持,那么我们可以从λ-演算理论中寻找众所周知的方法,这些方法允许我们从弱连续性推导出强一种这样的方法是基于描述[2]。一个发展是一个约简序列MdM1dM2d···,其中仅约简的红是初始存在于M中的任意红集合的残差。该方法是基于定理,如果所有的发展是有限长的,那么弱收敛意味着强收敛。在进一步讨论之前,我们注意到BRS可以比λ-演算更疯狂!一个在λ演算的案例分析中被反复使用的性质是,当一个项包含两个基数时,它们要么是不相交的,要么是嵌套的(一个在另一个里面)。这对于BRS中的基础红是失败的;更糟糕的是,它甚至对于它们下面的参数红也是失败的。事实上,图6显示了两个可能的参数化标记,它们是紧密包围的,每个部分在另一个内部。RxredexesySgAA′B′B见图6。 一个包含两个交织的红R和S的试剂gXy一BB′A′R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)6573我们不知道这个性质-然而,最近的研究探索了两种相互竞争的药物重叠的方式如果一个参数RedexR支持一个反应gdg0,那么对于某个参数a和连线ω ,r=(R<$ω)<$a出现在g中。类似地,如果RedexS支持反应gdg1,则s=(S)b发生在g中。基矢r和s可以以不同的方式重叠;例如,s可能不与R重叠,但可能与a部分重叠。研究确定了这种重叠的四种主要情况,并声称在某些进一步的条件下,弱连续图可以由g0完成dgJ和g0dJ. 由于这项工作尚未完成,我们确认,我们目前对BRS中的反应有两个不确定的认识:猜想1(ΛBIG中的弱连续)弱连续对于某些BRS中的某些主体集合成立,包括Λ子项在很大。猜想2(在BRS中的有限发展)对于某些BRS中的某些代理集,发展是有限的。总之,这两个结果将导致上述代理人的强烈一致性假设1是合理的,因为(如前所述)大部分分析已经完成。猜想2目前尚不明确。有可能的是,在大的情况下,发展只有在某种约束下才是有限结论这项工作的目的不是为λ -演算的一个变体找到丘奇-罗瑟定理的另一个证明,而是从这样的证明技术中学习,以便分析比迄今为止研究的更广泛的一类主体和反应规则的连续性这将导致更好地理解,不仅实际上有用的BRS,但也concilience本身。引用[1] Abadi,M.,卡尔代利湖,Curien,P-L.和Levy,J-J.(1991),明确的替代。Journal of FunctionalProgramming 1,pp375[2] 巴伦德雷格特H。Lambda Calculus:Its Semantics.(1984).北荷兰。[3] Bundgaard,M. Hildebrandt,T.(2006),具有本地名称的高阶移动嵌入式资源的Biographical语义。Proc. GT-VC 2005,Electronic Notes in Theoretical Computer Science 154(2),pp7[4] 詹 森 , O-H 。 和 Milner , R. ( 2003 ) , Bigraphs 和 transitions 。 Proc 30th ACM SIGPLAN-SIGACTSymposium on Principles of Programming Languages(POPL),2003,16页。[5] Jensen,O.H.和Milner,R.(2004年),《Bigraphs和移动流程》(修订版)。技术报告580,剑桥大学计算机实验室。可从http://www.cl.cam.ac.uk/users/rm135获得。74R. Milner/Electronic Notes in Theoretical Computer Science 175(2007)65[6] Leifer,J.和Milner,R.(2000),反应系统的互模拟同余。Proc.CONCUR2000,LNCS,第1877页,第243[7] Leifer,J.和Milner,R.(2006),链接图,转换和Petri网。出现在计算机科学中的数学结构。[8] 米尔纳河(2004),Bigraphs其名称有多个地方。技术报告UCAM-CL-TR-603,剑桥大学计算机实验室。可从http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-603.pdf获得。[9] O'Conchuir,S.(2006),Λsub作为显式替换演算(草稿)。
下载后可阅读完整内容,剩余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直接复制
信息提交成功