没有合适的资源?快使用搜索试试~ 我知道了~
Pi-演算LTS的性能优化
理论计算机科学电子笔记192(2007)5-11www.elsevier.com/locate/entcs一个性能良好的Pi-演算LTS(摘要)Pawel-Sobocin′ski1英国南安普敦大学ECS摘要π演算及其许多变体在文献中受到了广泛的关注。我们讨论了标准的早期标记的过渡系统(LTS),并概述了一种方法,该方法将系统分解成两个组件,其中之一是详细介绍。使用分解的优点包括更完整地理解Pi中绑定输出的处理,以及在添加和删除语言特征方面更鲁棒的LTS本文件概述了所涉及的一些技术和正在进行的工作的一些目标。保留字:Pi演算,进程演算,语义,标号迁移系统Pi演算[2,10]及其许多变体在文献中得到了广泛的研究。一个有效的批评是,在许多情况下,该理论是严重优化的特定变体研究在本文中,我们概述了一种方法,承诺提供一个更强大的方法,提供一个标记的过渡系统,例如,双相似性同意上下文等价。该技术也更易于推广,以追求捕获更广泛的微积分家族粗略地说,Pi演算沿着通道/名称扩展了二进制同步,这在CCS中很常见,它能够将名称作为参数传递。因此,输入前缀变成了一个绑定器,同步本身导致了绑定变量的通信名称的替换。演算从CCS将名称作为同步通信的一部分传递的能力意味着它在此设置中的行为相当不同特别是,限制的范围(CCS中是静态的)本质上变成了动态的,因为可以传递受限制的名称1由EPSRC赠款EP/D 066565/1部分支持的研究。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2007.10.0026P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience192(2007)5是吗?B一个!Bα在公共频道。此外,它的行为有点像一个新名字的全局生成器-因为α-转换确保了无论为一个受限制的名字选择哪一个具体的名字,它都与术语中的所有其他名字不同-事实上,新名字的全局性质也在互模拟的定义中得到了见[12]。Pi-演算的(归约)语义与CSS的语义非常相似,事实上,在无和片段中我们可以将其本质上表示为公理一个!b.P?x.Q→P<$Q[b/x](1)在求值上下文下关闭:并行组合和限制归约语义自然会导致一个上下文定义的等价:带刺的同余。虽然规范的,上下文定义的等价很难直接推理,因此定义另一个“语义”是有帮助的转换系统的标签旨在对可能的相互作用进行分类,环境保护 早同余与倒钩同余一致,但LTS因为共归纳的力量,它更容易使用。(IN)(OUT)一个!BP−−→P是吗?BQ−−→Q是吗?xP−−→P[b/x]一个!bP−−→PτJJ(COMM)一个!BPPJa/=b一个!(b)J是吗?BPQ−→PQJ−−→(O笔)P−→PQ−−→Qτb∈/fn(Q)(C输)一个!(b)第(1)款νbP−→PJP<$Q−→νb(PJ<$QJ)P−→ PJbn(α)<$fn(Q)=<$P−→PJb∈/n(α)αJ(PAR)PQ−→PQαJ(RES)νbP−→νbP所谓的早期LTS,上面为没有匹配或不匹配的有限、无和片段呈现,是众所周知的,并且可以以相当简单的方式被人类呈现和使用,只要遵循一些约定下面将更详细地讨论这些为了节省空间,我们省略了对称(C OMM)、(C LOSE)和(P AR)的不同版本;人们通常使用抽象语法,其中,Comm是结合的和交换的-这种语法上的等价关系通常被称为结构同余。值得一提的是,规则(OPEN)和(CLOSE)执行两个角色:作用域挤出和生成新的名称observable(绑定输出标签a!(b))。派生规则的附加条件值得进一步考虑。的对(RES)和(OPEN)的要求是相当明显的,并且继承自CCS从其范围外限制通道。 (CLOSE)的条件,(PAR)值得更多的关注内窥镜挤压机制功能正常。实际上,考虑过程P=(νb a!b)你是谁?x,其中限制的范围如果解除了(LPAR)上的侧条件,αJJP. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience192(2007)57就能推导出标签P一个!(b)第(1)款−→b?X. 但是,使用(关闭)时,你是不是应该去巴黎?y−→τ是的x的结果是,P的右分量在相互作用之后会变得不正确地结合关于(CLOSE)的边条件存在于类似的原因。即使有了副条件,互模拟的定义也必须改变。在一个!(b)第(1)款particular,如果PchleswithP−−→如果b∈fn(Q),则P_j_n_Q通常是唯一的. 根据(PAR)规则中的同一条件,我们称之为:考虑过程你好!b 和(νb a!b)cc!B这显然是等效的;第二个过程的第二个组件没有可观察到的行为(b)第二种行动不能。直观地说,这种现象证明了νSangiorgi和Walker [11,Convention 1.4.10]认为,所有这些问题都可以通过确保“......所考虑的任何进程或行动的绑定名称的选择应不同于所考虑的任何其他实体的自由名称."。这当然是真的,但可以说,这个约定是一个强有力的约定,撇开约定不谈,互模拟的定义已经被篡改了。许多作者也注意到,当使用证明助手或定理证明者时,对人类来说很好的约定是不容易实现的。已经有几个作品[1,6,4]旨在形式化这些约定,大致的想法是用可以出现在其中的名称集合来索引过程,并将互模拟视为名称索引关系。见[5]的概述和方法的比较如上所述,LTS可以被认为是推理约简语义上上下文定义的等价的工具;遵循这条推理路线提出了一个自然的问题,即LTS是否可以以某种系统的方式从约简语义中导出; Leifer和Milner [8]在这个方向上进行了研究,Klin,Sassone和作者[7]继续进行了研究在Leifer和Milnerc[−]语言的上下文c[−]。 粗略地说,对于闭项t,t−−→t当c[−]允许t在一步中减少到tJ,即c[t]→tJ和c[−]是最小的,上下文,换句话说,它不包含任何冗余信息,以便减少发生。最小性条件被明确地表达;如果术语和上下文的基本类别满足某些假设,则LTS上的双相似性(以通常的方式定义)是一个同余。该框架的局限性之一是,底层的归约系统需要由基本规则组成,这实际上排除了CCS和Pi等演算,因为归约规则包含参数在[7]J8P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience192(2007)5是开项,并且给定另一个开项,可以计算允许约简的最小上下文和最小参数。当工作正在进行时,在类似CCS的设置中,可能的标签的形式如下:-1a?x−2阿吉拉!bP,−1<$−→P<$−1其中上下文形成术语的(未经证实的)部分,并且标签能够修改上下文。另一个特征是标签中的信息受到一个缩减步骤中可以观察到的内容的限制我们可以使用从上面段落中描述的工作中获得的一些直觉来开发Pi演算的新LTS为了做到这一点,我们扩展了演算与类型的元语法洞和上下文,想法是这样的上下文可以形成一个术语的一部分后,互动。元语法是一个简单类型的lambda演算,β-归约构成了结构同余的一部分我们从一个非类型化的语法开始,在这个语法上我们给出了类型规则,从两个基本类型开始:名称类型N和进程类型P。在这种设置中,类型只是为了使元语法形式化,它们当然比基于通道类型的通常Pi演算类型系统具有更少的结构。与经典的表述不同,我们将ν视为一个标准的绑定器,它绑定了名称类型的变量 我们假设每种类型的变量都是可数的。 在所有这些选择中,我们的介绍更类似于Engberg和Nielsen实际上,该理论的所有基本成分(范围挤压,新名称生成)都已经在上述工作中出现;一个新颖之处是π演算的最大特点是变量和名称的语法类的崩溃。可以说,由此产生的简单性是具有欺骗性的。我们使用语法约定a,b表示名称常量,k,l表示名称类型项,x,y表示变量(包括名称变量),P,Q表示过程类型项,X,Y表示函数类型变量。类型上下文是从变量到类型的有限映射。我们将只考虑打字术语。类型σ::= N|σ →σ|σ → σ语法M::= X|一|0 |MM|米!MM|M?XM| νxM| λx:σ.M|M(M)类型规则a:N(:名)0:P(:ZERO)P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience192(2007)59k?国王!−→−→rM:PrMJ:Pr MMJ:Pr,x:NM:P(:PAR)ΓM:PΓk:NΓl:N你好!I.M:PΓ,x:NM:P Γk:N(:OUT PREF)Γ►νxM:P(:NU)你好x.M:P(:IN PREF)Γ(x)=σΓx:σ(:VAR)Γ,x:σ<$M:σJ(:λ)Γλx:σ.M:σ→σJΓ<$M1:σ→σJΓ<$M2:σΓ<$M1(M2):σJ(:APP)我们在下面简要概述了LTS中与沟通和范围扩展有关的部分它是从结构上定义的。因为我们在类型化设置中操作,所以LTS的状态是类型化上下文和术语对。我们在句法上将这样的对表示为|其中,Γ是类型上下文,V是项。类型上下文和术语之间的相互作用由类型保持来解释结果,下面描述了一个直观的帐户的过渡。片段中的标签是通常的CCS标签。 直观的想法是,在通道k上生成输出的过程可以执行与上下文,并演变成一个过程,该过程由其与交互上下文并行的延续组成,该交互上下文已被传递了所传达的名称。这个上下文在结果状态中被显式地描述为一个lambda抽象,I型变量=N→P(参见(O UT))。 另一方面,信道k上的输入可以执行与上下文的通信,获得一些名称-结果是一个lambda抽象,它绑定了一个类型为N的变量(cf(I n))。具有在k上输入的能力的过程与具有在所述信道上输出的能力的过程并行组合,可以执行同步而不需要外部上下文-抽象经由应用(cf(T au))组合。使用抽象和具体来表示后期语义在技术上有相似之处[9];参见下面的(COMM)规则。然而,请注意,我们没有说任何关于标签中传递的名称的实际性质。Ziegler、Miller和PalamidessiLTS -通信片段k?⟨ Γ |k?xP− → Γ |λx:N.P⟨Γ |P − → Γ |Uk?(IN)(中文)国王!⟨Γ|国王!lP−→Γ|λX:I.P<$X(l)<$⟨Γ|P−→Γ|T国王!(OUT)(OUT)⟨Γ|P<$Q<$− →<$r|λx:N.U(x)r|P<$Q<$− →<$r|λX:I.T(X)<$Q<$Y,Y:N|朴克?Y,Y:N|U(kk?年)的(vIN)Y,Y:N|啪!Y,Y:N|T(k/=y)国王!(vOUT)10P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience192(2007)5⟨ Γ |νyP − → r |λx:N.νyU(x)国王!⟨Γ|νyP−→r|λX:I. VyT(X)k?⟨Γ|P−→Γ|T|Q−→r|Uτ⟨Γ|P<$Q<$− →<$r|T(U)(TAU)P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience192(2007)511−→−→−→−→−→⟨Γ |P − →τ⟨ Γ |PjJ(TAU)Y,Y:N|P−→ττY,Y:N |PjJ(vTAU)⟨Γ|P<$Q<$− →<$r|PQ|νyP−→r|νyP⟩在规则(IN)和(νIN)中,结果右侧的变量x被选为U的fresh。类似地,在(ν OUT)和(νOUT)中,变量X被选为T的新变量。 LTS有一个规则的结构-每种标签都有一个公理-分别用于输入,输出和τ的(In),(Out)和(Tau)。此外,每个语法构造函数和每种标签都有我们给出一个简单的例子来演示上述规则是如何处理作用域挤压的首先,我们可以看到下面的转换:x:N|一个!x.Pa!x:N|λX:I.P<$X(x)<$(OUT)(vOUT)⟨∅|vxa!x.Pa!⟨∅|λX:I. νx(λX J:I.P<$X J(x))X<$但λX:I.νx(λXJ:I.P<$XJ(x))X<$λX:I.νx(P<$X(x)),因此,使用(TAU)我们得到了正确的范围挤压:⟨∅|是吗?y.Qa→?(IN)⟨∅|λy。Q|好啊!x.P−→a!⟨∅|λX:I. νx(P<$X(x))<$⟨∅|是吗?你好!x.Pτ⟨∅| vx.(P<$(λy.Q)(x))<$(TAU)从νx开始。(P<$(λy.Q)(x))<$νx(P<$Q[x/y]).可以证明关于LTS的类型保持结果- 事实上,假设r P:P。然后,下面的保持:• if r |P−k→?• 如果是|啪!• 如果是|Pτ⟨Γ|U→则Γ<$U:N →P;⟨Γ |T → T → I → P;⟨Γ |Pj ≠则Γ ≠ PJ:P.上面提出的LTS特别是,没有观察到所通信的名称的身份(输入、输出或新输出)。完整的LTS包含额外的标签和推导规则,这些规则通过适当地评估λ-抽象项来处理这些可观测量,从而产生标准的早期等价。因此,ν操作符的两个功能(作用域挤出和新名称生成)是单独处理的。速度。直观地说,从过程术语中产生的转换,如这里所介绍的,代表由过程控制的交互部分;从抽象术语中产生的转换,在本文中省略,代表由上下文控制的部分完整的LTS不需要复杂的边条件,变量约定,并且使用普通的bisim获得了所得到的等价性由类型上下文索引的单元。τ12P. Sobocin'ski/ElectronicNotesinTheoreticalComputerScience192(2007)5读者会注意到,事实上LTS与CCS的lts非常相似将名称传递给结果中的上下文(OUT)不等待一个在(IN)的结果中的名称)。这说明了一个特点和一个设计原则与LTS其思想是,演算的不同特征的语义应该由标准的LTS模块给出,这些模块以基本上正交的方式组合在一起:Pi演算用额外的特征扩展了CCS该技术在考虑以下因素时也很有用异步和更高阶的Pi变体。在每一种情况下,双相似性与上下文等价一致的事实的证明都是相当简单的-因此整个理论设置是相当稳健的。可以证明,本文所提倡的技术推广到其他结石与标准lts相比,标准LTS中的通信更加复杂-有两种不同的输出标签(自由和绑定)和两种不同的公理用于生成τ-转换。在那里,LTS上的双相似性与上下文等价一致的事实也依赖于语言中名字的相等性测试的存在引用[1] G. L.卡塔尼和P·休厄尔名称传递过程的模型:交错与因果。信息与计算,190:136[2] 联合Engberg和M.尼尔森一种具有标签传递的通信系统的演算技术报告DAIMI PB-208,奥胡斯大学,1986年5月。[3] 联合Engberg和M.尼尔森 一个演算的通信系统与标签传递-十年后。 在证明,语言和互动;纪念罗宾米尔纳的论文,第599-622页。麻省理工学院出版社,2000年。[4] G.联合法拉利,美国Montanari和M.皮斯托雷 名字传递演算的最小化转换系统:共代数公式。在proc 软件科学和计算结构的基础FoSSaCS,LNCS,第129-158页。施普林格,2002年。[5] M. P. Fiore和S.斯塔顿传名进程演算的操作模型比较。信息与计算,204(4):524[6] M. P. Fiore和D.图里名称和值传递的语义 在proc 第16届IEEE计算机科学逻辑年会,LiCS,第93-104页。IEEE Press,2001.[7] B. Klin,V. 是的,还有P。 所以,BOCN的KI。从基因组学角度看,这是一种基因遗传学。在计算机科学中的代数和余代数中,Calco '05,LNCS的第3629卷,第30-50页。施普林格,2005年。[8] J. Leifer 和 R. 米 尔 纳 推 导 反 应 系 统 的 互 模 拟 同 余 。 在 Proc. International Conference onConcurrency Theory Accuur,LNCS第1877卷,第243-258页中。斯普林格,2000年。[9] R.米尔纳通信和移动系统:Pi演算。剑桥大学出版社,1999年。[10] R. Milner,J.Parrow和D.沃克一个演算的移动过程,二。信息与计算,100(1):41[11] D. Sangiorgi和D.沃克π演算:移动过程理论。剑桥大学出版社,2001年。[12] L.维斯奇克 旧名为Nu。 Dagstuhl研讨会04241,2004年。[13] A. Ziegler,D. Miller和C. Palamidessi。一种用于名称传递演算的全等格式。在Proc.Workshopon Structural Operational Semantics SOS '05,ENTCS的第156卷,第169-189页,2006中。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 十种常见电感线圈电感量计算公式详解
- 军用车辆:CAN总线的集成与优势
- CAN总线在汽车智能换档系统中的作用与实现
- CAN总线数据超载问题及解决策略
- 汽车车身系统CAN总线设计与应用
- SAP企业需求深度剖析:财务会计与供应链的关键流程与改进策略
- CAN总线在发动机电控系统中的通信设计实践
- Spring与iBATIS整合:快速开发与比较分析
- CAN总线驱动的整车管理系统硬件设计详解
- CAN总线通讯智能节点设计与实现
- DSP实现电动汽车CAN总线通讯技术
- CAN协议网关设计:自动位速率检测与互连
- Xcode免证书调试iPad程序开发指南
- 分布式数据库查询优化算法探讨
- Win7安装VC++6.0完全指南:解决兼容性与Office冲突
- MFC实现学生信息管理系统:登录与数据库操作
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功