没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记162(2006)287-293www.elsevier.com/locate/entcs用BelnapAlban Ponse1 Mark B.van der Zwaag2荷兰阿姆斯特丹大学编程研究小组摘要概述了具有条件组合的ACP(即,如果-那么-否则)在贝尔纳普的四值逻辑上。有趣的是,ACP的大部分内容都可以使用这种逻辑进行分析。例如,选择操作+和δ(死锁)都可以被看作是条件复合的实例,从这个角度可以得出公理x+δ=x。此外,并行组合还可以推广到条件并行组合,它以顺序组合为例,仅次于普通并行组合、纯交错和同步ACP。本文是[12]的延伸摘要。全文包含GACP中并行调度的所有证明和一些示例。关键词:多值逻辑,贝尔纳普逻辑,过程代数,ACP,条件合成,选择1引言1994年,Jan Bergstra和他的同事们经历了一场关于发散、错误和恢复或异常处理的数据库规范的复兴。这是由诸如VDM [8]和即将到来的对Java [6]的兴趣等语言引发的。第一个成果是Bergstra,Bethke和Rodenburg的一篇关于四值命题逻辑的文章[2]。因此,认为通过条件组合构建(即,一个if-then-else运算符)是显而易见的,第一篇涉及Kleene三值逻辑的论文如果φ那么P否则Q条件φ可以取Kleene 这导致了[5],其中[2]的逻辑与ACP相结合,论文中使用了其他非经典逻辑,并最终使用了ACP的四值逻辑C4,条件1电子邮件地址:alban@science.uva.nl2电子邮件:mbz@science.uva.nl1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.12.102288A. Ponse,M.B.van der Zwaag/Electronic Notes in Theoretical Computer Science 162(2006)287组成(在[11]洗礼“非加太的逻辑”)。在[11]中,我们证明了这个逻辑(有一个顺序连接词)等价于Kleene的三值逻辑的自然扩展,它有第四个真值(有对称连接词)。直到两年前,我们才发现后一种逻辑是贝尔纳普[7]的文件。在这篇文章中,我们专注于过程代数条件复合贝尔纳普的逻辑。ACP的一个棘手的角落是选择和僵局的结合。人们经常读到,过程x+y在x和y之间做出选择。然而,这对于a+δ来说并不正确,其中a是一个动作,δ代表死锁(实际上,标准的ACP公理是x+δ=x)。在这种情况下,选择可以被看作是一种规定性的操作吗?在这篇文章中,我们表明,它可以:有一个简单的对应条件组成的贝尔纳普的逻辑,允许一个解释的性质选择过程代数从逻辑的角度来看。我们将替代复合+推广到条件复合+φ,使得x+y=x+By其中B(both)是真值,代表真和假。我们只非正式地描述我们的结果;所有的证明都可以在[11,12]中找到2贝尔纳普贝尔纳普3否定被定义为对合(满足x=x),<$B=B,<$T=F,<$F=T,<$N=N,合取和析取是分配格的最大下界和最小上界不联系我们B N联系我们F《易经》云:“七经”。这种将逻辑描述为具有对合的分配格的特征直接导致了有限和完全的等式公理化[11]。现在我们在这些真值上定义一个替代逻辑C4,它只有一个三元运算D,称为条件复合。此操作定义为:XTDy=x,xFDy=y,x NDy= N,[3]贝尔纳普将B作为数据库查询结果冲突的结果,将N作为答案缺失的结果。A. Ponse,M.B.van der Zwaag/Electronic Notes in Theoretical Computer Science 162(2006)287289(C1)x(uvDw)Dy=(xuDy)vD(xwDy)(C2)(xwDy)vD(xJwDyJ)=(xvDxJ)wD(yvDyJ)(C3)(xwDy)wDz=xwD(ywDz)(C4)不xDF=x(C5)xTDy=x(C6)xFDy=y(C7)xNDy=N(C8)XBDy=yBDx(C9)XBDN=x(C10)Bx=B表1C4公理且xBDy=xHy,其中H是格中x和y的最小上界B联系我们T F联系我们N所谓的信息(或知识)排序[2,7]。 条件合成有一个操作性的、顺序的解读:在xyDz中,首先对y进行求值,根据结果,可能是x和/或z。 在表1中,我们给出了C4的一套完整的公理.逻辑B4和C4具有完全相同的表达能力,也就是说,它们的运算可以相互定义:使用B,T,F,我们有<$x=FxD T,xy =(yxDF)BD(xyDF),反之亦然,使用N,xy D z =(x <$y)<$(z <$$>y)<$(x <$z<$N)<$(y <$$>y <$N)。因此,这两种逻辑可以被认为是我们证明了关于信息序的单调函数的逻辑是真函数完备的设f是(k + 1)元单调函数,且f为(k+1)元单调函数. 当我听到你的声音时,f(x′,y)=f(x′,N)H(f(x′,T)yDf(x′,F))H((NyDf(x′,B))yDN).290A. Ponse,M.B.van der Zwaag/Electronic Notes in Theoretical Computer Science 162(2006)287(G1)x+φQ<$Qχy=(x+φy)+<$(x+χy)(G2)(x+φy)+φ(xJ+φyJ)=(x+φxJ)+φ(y+φyJ)(G3)x+φ(y+φz)=(x+φy)+φz(G4)(x+φy)z=xz+φyz(G5)(xy)z=x(yz)(G6)x+Ty=x(G7)x+Fy=y(G8)x+Ny=δ(†)x+φy=x+φy, 如果C4φ=φ表2 GBPAδ公理通过引入,该函数是可扩展的(例如,对于所有值a,f(x′,a)是可扩展的)。3进程代数中的条件合成我们现在来看一下GBPA δ,它是BPA δ(带有deadlock的基本进程代数,其中包含用于死锁的常量δ和一个长期的composition+)的推广。在GBPA中,δ替代复合用C4项φ参数化,因此得到称为条件复合的运算+φ,并且x+φy被读为如果φ则xelsey。 公理系统GBPAδ由表2中的公理组成。死锁对应于公理G8中的+N,而替代组合可以看作实例+B,如下所示。接下来,我们给出了一个操作语义的过程封闭的条款,也就是说,不包含过程变量的过程条款。设W是C4项的赋值集,设A是作为参数的动作符号的非空集合的公理系统,并设A×W是转移标签的集合。 过渡规则在表4的上部给出,其中具有标签a,w在估值W下对动作A的执行进行建模。我们像往常一样定义(强)互模拟过程闭项是双相似的(A),如果它们通过互模拟相关。由于双相似项对于每个赋值都有匹配的动作步骤,我们允许逻辑中的(用户定义的)命题,其赋值在整个过程的执行过程中可能不是恒定的转换规则是panth格式[13],由此可以得出双相似性是一个同余。此外,GBPAδ公理是合理和完整的[11,12]。我们的断言+等于+B是通过证明BPAδA. Ponse,M.B.van der Zwaag/Electronic Notes in Theoretical Computer Science 162(2006)287291⊆⇔在GBPAδ中可导出。替代合成的交换性由下式导出:x+By=(y+Fx)+B(y+Tx)=y+FQBQTx=y+Bx使用公理G6、G7、G1、C8和C4。关联性是G3的一个实例。特性:x+Bx=(x+Ty)+B(x+Ty)=x+TQBQTy=x使用G6、G1和C4xBDx=x。顺序合成对替代合成的右分配性是G4的一个实例。公理x+δ=x可以由下式导出:x+Bδ=(x+Ty)+B(x+Ny)=x+TQBQNy=x使用G6、G8、G1和C9。最后,公理δx=δ可以用G8和G4导出。我们发现,过程代数和逻辑条件合成是非常相似的,当人们比较它们的公理时,这一点变得显而易见。信息序(≤)的过程代数对应是被加数包含序(≤定义为xyx+y=y。 所以替代成分可以说是的配对物BD,而δ对应于N。 以下结果意味着,C4描述了选择和死锁:命题3.1对于i = 1,2,设p i是一个开过程项,其中没有动作符号出现,唯一的运算是条件合成。 设ti为C4项,由pi通过将+ φ解释为φD,δ解释为N而得到,其中过程变量也表示命题。 则GBPAδ/A|= p1p2iC4|= t1≤t2,因此GBPAδ/A|= p1= p2iC4|= t1= t2。4广义并行复合GACP(Generalized ACP)是用一个作用对称的非空集合A和一个交换结合函数来参数化的|:A×A→A{δ},它定义了哪些动作进行通信。它扩展了GBPAδ,并推广了并行组合的条件φ,其中条件φ涵盖了交织和同步,并且同步器可以确定执行顺序。 此外,它还有一个辅助的广义左归并和广义通信归并φ|封装操作H,它将动作从H A重命名为δ。这些公理是GBPAδ的公理,其中有四个简单的封装公理(此处省略)和表3中的公理。操作TB限制为交织(自由合并),而Fofor∈{B,T,F}定义同步合并,TT表示顺序组合。一些典型的身份:xφy=y φx,x φ|y= y φ|<$x和δ φ|x = δ。转换规则见表4。双相似性是一个全等性,所有公理在这样得到的模型中都是合理的。平行组合292A. Ponse,M.B.van der Zwaag/Electronic Notes in Theoretical Computer Science 162(2006)287(GM1)xφy =(x φy + y φ x)+ φ(x φ|y +|<$<$x)(GM 2)aφ<$<$x= ax(GM3)axφy=a(xφy)(GM4)(x+φy)χz=xχz+φyχz(GM5)aφ|b = a |B(GM6)aφ|bx =(a |b)x(GM7)轴φ|b =(a |b)x(GM 8)axφ|A=(a|b)(xφy)(GM 9)(x + φy)|χz = x |χz + φy |χz(GM 10)zφ|(x+ χy)=zφ|x+ χzφ|埃什基表3A上广义merge;a,b range的运算可以从过程封闭项中删除,因此GACP对于这些项是完备的。5结论我们认为,条件成分在贝尔纳普我们进一步指出,条件组合可用于定义顺序连接词,如Mc-Carthy的直接连接词[10],left s equu e n t ia l conjun c t i o n t [ 2 ]和fitting n g的→ n t i o n t i n g [ 7 ]。例如,在一个示例中,xy=yxDF. 最后,我们注意到,广义合并可以用来模拟并行调度,见[11,12]的例子。引用[1] N.D.贝尔纳普有用的四值逻辑在J.M. Dunn和G. Epstein,editors,Modern Uses of Multiple-ValuedLogic,pages 8-37,D. Reidel,1977年。[2] J.A.伯格斯特拉岛Bethke和P.H.罗登伯格一个命题逻辑有四个值:真,假,发散和无意义。Journal ofApplied and Non-Classical Logics,5(2):199-218,1995.[3] J.A. Bergstra和J. W.克洛普同步通信的进程代数。Information and Control,60(1/3):109-137,1984.[4] J.A. Bergstra和A.庞塞Kleene的三值逻辑与过程代数。Information Processing Letters,67(2):95-103,1998.[5] J.A. Bergstra和A.庞塞进程代数与四值逻辑。Journal of Applied Non-Classical Logics,10(1):27-53,2000.[6] G. Bracha等,Java语言规范(第2版)。艾迪森·韦斯利2000年[7] M.C.拟合Kleene的三值逻辑及其子逻辑。Fundamenta Informaticae,20:113-131,1994.A. Ponse,M.B.van der Zwaag/Electronic Notes in Theoretical Computer Science 162(2006)287293√−→−→−→−→B=cx−→x/J−→JJ厶a−→厶X厶xy−→y厶X厶xy−→xJxJy厶XxJ/n,w(φ)∈ {B,T}xa,wxJ/n,w(φ)∈ {B,F}a,w a,wx+φy−→x/y+φx−→x/a,wx xJ/,w(φ)∈ {B,T},w(φ)∈ {B,T}−→xφ厶y−→ (xJ/10)φa,wx xJ/,w(φ)∈ {B,T},w(φ)∈ {B,F}−→yφ厶x−→ yφ(xJ/10)a,w b ,wxxJ/,yyJ/,a|b=c,w(φ)∈ {B,F},w(φ)∈ {B,T,F}−→ −→X φǁψc、wy−→ (xJ/10)φǁψ(yJ/h)厶XxJ/b,yb,wyJ/a|a,w jxφ|ψc、wy−→ (xJ/10)φǁψ(yJ/h)xφ厶y−→ (xJ/10)φ厶XxJ/n,a/∈Ha,wH(x)−→H(x/)表4过渡规则。a,b,c∈A;w∈W;xJ/J在P上的值域,其中P是√andy√/√ √ √ √过程封闭项;和=φx=x,φǁψ2016 - 05 -25 00:00:00)=的[8] C.B.琼斯使用VDM进行系统软件开发(第2版)。Prentice-Hall International,Englewood Cli Clens,1990年。[9] S.C.克林 关于序数的符号。 《符号逻辑》,3:150-155,1938年。[10] J·麦卡锡计算的数学理论的基础。 在P.Bra Bauort和D. Hirschberg(eds.),计算机程序设计和形式系统,第33-[11]A. Ponse和M.B.范德兹瓦格。ACP的逻辑报告SEN-R 0207,CWI,2002年。[12] A. Ponse和M.B.范德兹瓦格。使用贝尔纳普逻辑的ACP的一般化。发表于Journal of Logic and AlgebraicProgramming。−→√−→294A. Ponse,M.B.van der Zwaag/Electronic Notes in Theoretical Computer Science 162(2006)287[13] C.维尔霍夫带有谓词和否定前提的结构化操作语义的一个同余定理。Nordic Journal of Computing,2(2):274-302,1995.
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- IPQ4019 QSDK开源代码资源包发布
- 高频组电赛必备:掌握数字频率合成模块要点
- ThinkPHP开发的仿微博系统功能解析
- 掌握Objective-C并发编程:NSOperation与NSOperationQueue精讲
- Navicat160 Premium 安装教程与说明
- SpringBoot+Vue开发的休闲娱乐票务代理平台
- 数据库课程设计:实现与优化方法探讨
- 电赛高频模块攻略:掌握移相网络的关键技术
- PHP简易简历系统教程与源码分享
- Java聊天室程序设计:实现用户互动与服务器监控
- Bootstrap后台管理页面模板(纯前端实现)
- 校园订餐系统项目源码解析:深入Spring框架核心原理
- 探索Spring核心原理的JavaWeb校园管理系统源码
- ios苹果APP从开发到上架的完整流程指南
- 深入理解Spring核心原理与源码解析
- 掌握Python函数与模块使用技巧
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功