没有合适的资源?快使用搜索试试~ 我知道了~
► ⟨⟩↔ ⟨⟩可在www.sciencedirect.com在线获取理论计算机科学电子笔记305(2014)5-18www.elsevier.com/locate/entcsPDL中的双相似和逻辑等价程序马里奥河F. Benevides贝内维德斯1,2里约热内卢联邦大学计算机科学系和系统与计算机工程专业巴西摘要在标准的命题动态逻辑(PDL)文献[5,16,4]中,语义由标记转换系统给出,其中对于每个程序π,我们关联一个二元关系Rπ。 进程代数[1,8,10,2]也通 过 标 号 转 移 系 统 给出了进程(项)的 语 义 。在这两种形式中,PDL和进程代数,比较进程的关键概念是互模拟。在PDL中,我们也有逻辑等价的概念,它可以用来证明两个程序π1和π2在逻辑上是等价的。不幸的是,逻辑等价和互模拟在PDL中不匹配。双相似程序在逻辑上是等价的,但反之则不成立。本文提出了一个语义和公理化的PDL,使逻辑上等价的程序也是双向相似的。我们证明了可靠性、完备性和有限模型性质。关键词:互模拟,命题动态逻辑,模态逻辑1动机在标准PDL文献[5,16,4]中,语义由标记转换系统给出,其中对于每个程序π,我们关联一个二元关系Rπ。顺序复合和非确定性选择算子分别定义为关系的复合和联合Rπ1;π2 = Rπ1 <$Rπ2Rπ1<$π2 =Rπ1<$Rπ2进程代数[1,8,10,2]也通过标号转移系统给出了进程(项)的语义。在PDL和Process Algebra这两种形式中,比较进程的关键概念是互模拟。在PDL中,我们也有逻辑等价的概念,它可以用来证明两个程序π1和π2在逻辑上是等价的(其中π1是参与者π2是指在执行1这项工作得到巴西研究机构CNPq和CAPES的支助2电子邮件:mario@cos.ufrj.brhttp://dx.doi.org/10.1016/j.entcs.2014.06.0021571-0661/© 2014 Elsevier B. V.保留所有权利。6M.R. F Benevides/理论计算机科学电子笔记305(2014)5程序的πi公式(?)不幸的是,逻辑等价和互模拟在PDL中不匹配。双相似程序是逻辑等价的,但反之则不成立。例如,取程序π1=a;(π3<$π4)和π2=a;π3<$a;π4a;(π3<$π4)参与者a(π3π4)参与者aπ3 aπ4参与者a参与者a;π3α;π4β但不难看出π1和π2是非双相似的程序,因为在π1上第一步之后,它到达π3<$π4,这与π2上的两种可能性:π3或π4都不匹配。π2一◦Sπ3Jcz轴π4Jcπ3◦Sπ1一J.C.Jz轴Fig. 1. 非双相似程序关于跟踪语义的一个有趣的讨论出现在[2]中。他们定义和比较具体的顺序过程的各种语义,并为它们提供代数公理化和语义模态表征(无模态公理化)。这项工作的主要动机是提出一个新的语义PDL,基于痕迹与上下文,它匹配的概念,逻辑等价和互模拟,即。例如,两个程序π1和π2在逻辑上是等价的(π1π2参与(2)当且仅当它们是双相似的。我们提供了一个公理化和证明完整性w.r.t这个新的语义。证明完备性产生有限模型性质和可判定性。值得注意的是,我们的贡献是在PDL上,而不是在过程理论上。2命题动态逻辑在本节中,我们介绍PDL的语法和语义定义2.1PDL语言由一个可数命题符号的集合Φ,一个可数基本程序的集合φ,布尔连接词组成。<$和<$,程序构造器;,,和,以及每个程序的模态π一π4M.R. F Benevides/理论计算机科学电子笔记305(2014)57πππ。 公式定义如下:::= p|不|¬ϕ |ϕ1∧ ϕ2|π|π1; π2|π1∪ π2|ππ,其中p∈Φ,a∈φ。在本文中出现的所有逻辑中,我们使用标准缩写⊥ ≡ ¬T,ϕ∨φ ≡¬(¬ϕ∧ ¬φ),ϕ→φ ≡¬(ϕ∧ ¬φ) and [π] ϕ≡ ¬⟨π⟩¬ϕ.定义2.2PDL的帧是元组F=(W,R),其中- W是一个非空的状态集合;- R={Ra|a ∈ <$},Ra是W上的二元关系,对每个基本程序a ∈ <$;- 对于每个非基本程序π,我们可以归纳地定义一个二元关系Rπ,如下所示• Rπ1;π2 = Rπ1 Rπ2,• Rπ1<$π2=Rπ1<$Rπ2,• Rπs = R,其中R是R π的自反传递闭包。定义2.3PDL的模型是一对M=(F,V),其中F是PDL框架,V是赋值函数V:Φ→ 2W。定义2.4设M=(F,V)是一个模型。模型M在状态w下满足公式M的概念,记为M,wD,可以归纳定义如下:- M,wDpi∈V(p);- M,wDT总是;- M,wDiM,w/D;- M,wD≥1≤2≤M,wD≥1和M,wD≥2;- M,wDi有wJ∈Ws. t. wRπWJ和M,WJDπ.例2.5M,wD <$(π1;π2)<$p i<$p有wJ∈Ws. t. wRπ1;π2WJ和M,WJDp,i ∈有WJ∈Ws. t.wRπ1<$Rπ2wJ和M,wJDpπ1;π2Wπ1Jcπ2zJcp wJ3过程演算在本节中,我们提出了一个非常小的进程(程序)演算的PDL程序在前面的第2节。我们证明了两个过程是双相似的,当且仅当它们具有相同的有限可能运行集。这是一个启发[2]。8M.R. F Benevides/理论计算机科学电子笔记305(2014)51K11K21Kn√α√α→αα.π→ παπ→α π′π;τ→π′;ταπ→ π′απ+τ→π′βτ→ τ′βπ+τ→τ′απ→ π′απ→ π′;π表1过渡关系设N ={a,b,c,. . . }是一组名称或动作,用α,β............................................表示,语言可以定义如下。π::= α|π1; π2|π1 + π2|ππ,其中α∈ N我们用π和τ表示过程(程序),用α、β和γ表示动作。我们用ieπ→απj表示过程π能实现απα,之后,beh ave作为πJ。我们用π→απ来表示π的过程是成功的在执行动作α之后完成。 一个过程完成时,没有可能的β剩下的动作让它去执行。例 如 ,β →。我们的进程演算的语义可以由下表中的转换规则给出。互模拟的概念是任何进程代数中的一个关键概念。它是具有相互相似行为的进程之间的等价关系。直觉是两个双相似过程不能被外部观察者区分。定义3.1设P是所有过程的集合。一个集合Z<$P×P是一个强互模拟,如果(π,τ)∈Z蕴涵以下内容:• 如果π→• 如果τ→πJ,则有τJ∈Psuc h使得τ→ατJ,则有πJ∈Psuc h使得π→ατJ和(πJ,τJ)∈Z;πJ和(πJ,τJ)∈Z;• π→ 当且仅当τ→ατ。定义3.2两个过程π和τ是强双相似的(或简单的双相似),记为π<$τ,如果存在强互模拟Z使得(π,τ)∈Z。命题3.3π1;(π2+π3)/ππ1;π2+π1;π3见图1。3.1使用Context在本节中,我们介绍了有限可能运行的关键概念,一个过程。这个概念在我们的逻辑语义学中起着核心作用定义3.4一个带有连续文本的序列,记为y−→αc,是一个动作序列和有限个动作集,其形式为α1{β1···β1}.α2{β2···β2 },···.αn{βn···βn}。···,αααM.R. F Benevides/理论计算机科学电子笔记305(2014)591Ki其中αi∈{βi···βi},其中1≤i≤ n。10M.R. F Benevides/理论计算机科学电子笔记305(2014)5···−→c→→1K11K21KnFF⇒}⇒⇒1设−→αc=α1C1.α2C2.αnCn是一个有限的连续n元数序列,则f−→αc的长度为n.定义3.5设−→αc=α1C1.α2C2·· ·.αnCn,β=β1D1.β2D2···.βnDn具有长度为n的上下文的作用序列。 我们定义了一个严格的偏序序列的行动与上下文如下−→αc−→βci,对于alli,1≤i≤n,αi=βi,CiDi,对于至少一个i,Ci∈Di。定义3.6设−→αc=α1{β1. β1}α2{β2. β2}.αn{βn·· ·βn}是a序列行动与文字。我们知道−→αc匹配一个概率π0,如果π0α1π1α2π2·· ·πn−1→αnπn且对所有i,0≤in,{αi,βi· · ·βi}都是有πi的空间可以执行。1ki我们用π−→αcπj表示−→αc矩阵π,并给出了πm过程−→cJ−→αc动作序列α 然后表现为π。 我们写ππ来表达−→αc满足π,过程πm ay在执行了一系列的函数−→αc之后成功地完成(这特别意味着−→αc是有限的)。定义3.7我们定义了一个过程的上下文的有限可能运行的集合π,记作by−R→c(π),如−R→c(π)={−→αc:π−→αc<$。为了获得互模拟和逻辑等价之间的期望关系,我们引入了具有进程上下文的有限可能运行的概念,即,这些过程成功完成的情况。因此,我们提出了一些有用的结果有限可能运行的上下文。重要的是要注意,在我们的进程演算中,所有进程,在其执行的任何状态下,只能执行有限的一组动作,即,他们是形象有限的。定义3.8设R和S是具有上下文的有限动作序列的集合。我们可以在这些集合上定义以下运算(i) RS={−→αc. −→βc:−→αc∈R和−→βc∈S};(ii) R<$S={−→αc:−→αc∈R或−→αc∈S};(iii)R0={−→ε},Rn=R<$Rn−1(n≥1);(iv)R=n∈NRn.引理3.9若π<$τ,则对每个−→αc,π−→αc<$i<$τ−→αc<$。⇒ ⇒这个引理的证明可以在附录A中找到。这个证明是基于[3]中提出的类似证明引理3.10如果对每个−→αc,π−→αc<$当且仅当τ−→αc<$,thenπ<$τ是的。 当τ−→αc和π/πτ时,则有π−→αc和o。则存在αsuc hπ→α1π1⇒对于所有的τ1或者τα⇒τ1(1)或π11τ1(2)。 但(1)不可能是真的,M.R. F Benevides/理论计算机科学电子笔记305(2014)511FFFFFFFFFFFFF因为它与π和τ能够执行相同的动作集合的假设相矛盾,因为如果α1是a−→αc的某个序列中的第一个a,则它的上下文包含π和τ可以执行的所有操作仅存的可能性是(2),π1/πτ1。如果我们对π2τ2等应用相同的推理,对于πi/πτi,πi和τi必须能够执行相同的动作集合。由于所有过程最终都终止,我们最终必须达到一对πn和τn,使得πnτn和πn和τn必须能够执行相同的动作集γ1,···γkn√ √ √n n且πn=或τn=或两者皆πn=τn=。前两种情况不是这是可能的,因为πn和τn必须能够执行相同的一组动作,并且πn不执行任何动作,并且πn的任何进程必须能够执行至少一个动作。 因此,唯一的可能性是πn=τn=π n,由此得出:πn<$τn,这是一个矛盾。因此,ππτ。Q定理3.11ππτ当且仅当−R→c(π)=−R→c(τ)。是的。 (3)证明了−→αc∈−R→c(π). 然后,π−→αc<$。Asππτ,这意味着,byF−→cα⇒−→−→引理3.9,thatτ,whi c h表示that−→αc∈−R→c(τ)。 因此,Rc(π)<$Rc(τ)。f f f−R→c(τ)→−R→c(π)的过程完全类似。(1)假设−R→c(π)=−R→c(τ)。 通过−R→c(π)和nd−R→c(τ)的定义π−→αcf f f f−→αc当且仅当τ. 根据引理3.10,ππτ。Q接下来,我们提出了有限可能运行集合之间的一些等式,这些等式对我们公理化的可靠性证明定义3.12设−→αc=α1C1.α2C2· · ·.αnCn∈−R→c(π1),{γ1,·· ·,γm}是π2能执行的所有动作的集合,C1J=C1<${γ1,·· ·,γm}并且C1JJ=C1\{γ1,· · ·,γm}. 我们的定义• −→αc|+π2= α1C1J.α2C2· · ·.αnCn• −→αc|−π2= α1C1J J.α2C2·· ·.αnCn• −R→c(π1)|+π2={−→αc|+π2|−→αc∈R−→c(π1)}• −R→c(π1)|−π2={−→αc|−π2|−→αc∈R−→c(π1)}定理3.13下列集合等式成立:(i)−R→c(α)={α};(ii)−R→c(π1;π2)=−R→c(π1)<$−R→c(π2);12M.R. F Benevides/理论计算机科学电子笔记305(2014)5FFFFF(iii)−R→c(π1+π2)=−R→c(π1)|+π2<$−R→c(π2)|+π1;(iv)−R→c(π)=(−R→c(π))π。证据 从表1中可以直接证明。QM.R. F Benevides/理论计算机科学电子笔记305(2014)513ππ4PDL+在本节中,我们提出的语言,语义和公理系统的命题动态逻辑与非确定性的选择操作。4.1语言与语义该语言类似于定义2.1中的语言,其中我们将+替换为。::= p|不|¬ϕ |ϕ1∧ϕ2|π|π1; π2|π1+ π2|ππ,其中p∈Φ,a∈ N。定义4.1PDL+的帧是元组F=(W,Ra),其中- W是一个非空的状态集合;- Ra是W上的二元关系,对每个基本程序a∈n;- 对于每个非基本程序π,我们可以归纳地定义一个二元关系Rπ,如下所示• Rπ1;π2 = Rπ1 Rπ2,• Rπ1+π2 ={(s,t)|[(s,t)∈ Rπ1且R πr(s,r)∈ Rπ2]或[(s,t)∈Rπ2且<$r(s,r)∈Rπ1]}• Rπs = R,其中R是R π的自反传递闭包。PDL+模型和PDL+满意度的语义概念与定义2.3和2.4中PDL的定义如果M,wD对每个状态w都满足,我们说,在模型M中,M是全局满足的,记为MD。如果在一个框架F的所有模型M中都全局满足,我们说在F中,符号FD是有效的。最后,如果在所有框架中有效,我们说有效,记为D。如果D是Participant,则两个公式和在语义上是等价的。提案4.2π1;(π2+π3)证据 设M是基于框架波纹管的模型,V(p)={v}。 很容易以验证M,w<$π1;(π2+π3)<$p和M,wDπ1;π2+π1;π3pWπ1◦Sπ3vJcz轴π3JCQ接下来的定义和引理将我们的语义与上下文的可能运行联系起来π2◦14M.R. F Benevides/理论计算机科学电子笔记305(2014)5F≥Fc∈−R→cJFFc−→c≥MM01n nFFFFc−→cF1Ki我FFFFFFFFFFFF定义4.3设F =(W,Rα)是一个框架,(v0,v1,..., vn),n1,是在且−→α(π)中的一条长度为n的有限路,是一个过程为π的连续序列. Wesaythat−→αc匹配路径(v0,v1, . ,vn)forr对于所有i,1≤i≤n,(−→αc)i=αi{βi. βi}和(vi−1,vi)∈Rα,且对于对所有βj, 1≤j≤ki,存在一个w满足(vi−1,w)∈Rβ. Wesaythat−→αc完全匹配路径(v0,v1,., vn),如果存在唯一的w使得(vi−1,w)∈ Rγ,对所有的 γ ∈{βi···βi}且1 ≤i≤ n。1ki一个frameF在状态wi n匹配一个概率π,对于ll−→αc∈−R→c(π),存在一个路ρ,在F中,使得−→αc满足ρ。引理4.4M,wD <$π<$i <$F在w处匹配π,存在有限路(v0,v1,.,vn),n≥1,使得v0=w,M,vnD<$且re是−→α∈R(π),长度为n,使得-→αc匹配路径p(v0, . ,vn)。这个引理的证明可以在附录B中找到。其次,我们给出了这一节的主要定理,它建立了双相似程序与逻辑等价程序之间的定理4.5−R→c(π)=−R→c(τ)当且仅当D<$π <$p参与τ<$p。是的。 (1)假设−R→c(π) =−R→c(τ),但/D <$π <$p参与τ<$p。那么,我们走吧在不失一般性的情况下,假设存在模型M和状态v0,模型使得M,v0D <$π<$p(1),但M,v0<$τ <$p(2)。根据引理4.4,(1)意味着有一条路径(v,v,...,v),n1,使得v D p(3)且有−→αc∈−R→c(π)使得m在c处是这条路. 但当−R→c(π)=−R→c(τ)时,则−→αc∈−R→c(τ)。根据定义4.4,这和(3)意味着M,v0D<$τp,这与(2)相矛盾。(1)D <$π<$p参与τ<$p(1),但−R→c(π)−R→c(τ). 那么,我们走吧假设,在不损失一般性y的情况下,存在−→αcsuc h,使得−→αc∈−R→c(π),但是−→αc/∈−R→c(τ),且re是no−→βc∈−R→c(τ),则c h使得−→βc≠−→αc。让我们建立一个框架,它匹配π,它由一个有限树组成,有一个p a th(v0, . ,vn),n≥1,使得−→αc恰好是路(v0, .. . ,vn)forr过程π。设M=(F,V)是一个模型,使得V(p)是唯一元素为vn的单点模型,vn∈ V(p). 然后,我们有一条 路径(v0,..., vn)使得M,vnD p且−→α∈R(π)满足这条路径。 根据引理4.4,M,v0D<$π<$p.当−→αc/∈−R→c(τ)且r∈是no−→βc∈−R→c(τ)时,满足−→βc∈−→αc,soas−→αc,其中c恰好是路径(v0, . ,vn),则(v0, . ,vn)isnot与过程τ的任何其他序列匹配。除此之外,没有其他路径(v0,...,vm),m≥1,使得M,vmDp,因为F是一棵树。 因此,根据引理4.4,M,v0/D<$τp,这与(1)相矛盾。QM.R. F Benevides/理论计算机科学电子笔记305(2014)515推论4.6π τ当且仅当D π p参与τ p。16M.R. F Benevides/理论计算机科学电子笔记305(2014)5证据 它直接由定理3.11和4.5导出。Q4.2公理化我们使用标准的布尔型缩写“”、“”、“→”和“Participate”,并使用以下缩写来表示“”:[π]:=π。下面给出的公理化是标准PDL证明理论,扩展了非确定性选择的新公理公理1. 所有的同义反复,2. [π](π→π)→([π]π→[π]π),3. [π1;π2]参与[π1][π2],4. <$π1+π2<$p参与(<$π1<$p<$$>π2<$p)<$(<$π1<$T <$$>π2<$T),5. [π<$]参与者[π][π<$],6. [π](→[π])→([π]→[π]),推理规则M.P.,→/U.G./[π]公司简介其中σ是一个映射,它一致地将公式替换为命题变量。公理1,2,3,5和6以及推理规则是PDL中常规程序的标准[5,16,4]。公理4需要一些解释。它可以重写为<$π1+π2<$p参与者(<$π1<$p<$$>π2 <$T)<$(<$π1<$T <$$>π2<$p)直观的含义是“每当我们执行一个非确定性选择π 1 + π 2时,我们必须能够执行π 1或π 2,但两者都必须可供执行。这就是<$πi <$T(i = 1,2)所保证的,即,可以执行πi。例4.7M,wD <$(π1+π2)<$p和M,vπ(π1+π2)πpWπ1p,svπ1zpJc4.3可靠性和完备性为了证明可靠性,有必要证明每个公理在这类框架中是有效公理1、2、3、5和6的有效性以及推理规则从PDL文献[5、16、4]中是众所周知的。下面,我们给出公理4的证明引理4.8下面的公式是有效的:D <$π1+π2<$p参与(<$π1<$p<$$>π2<$ p)<$$>(<$π1<$T <$$> π2<$T)这个引理的证明可以在附录Cπ2M.R. F Benevides/理论计算机科学电子笔记305(2014)517中找到。18M.R. F Benevides/理论计算机科学电子笔记305(2014)5定理4.9(合理性):PDL+是合理的。定理4.10(有限PDL+模型的完备性):命题动态逻辑PDL+关于 有限PDL+模型类是完备的。这个定理的证明可以在附录D中找到。4.4决策性和复杂性第4.3节证明了PDL+对于有限PDL+模型类是完备的。因此,它具有有限模型性质,而且,每个相容公式都可以在模型的一个状态下满足,其中至多2 |ψ|得双曲余切值.|是符号的个数。|is the number of symbols of ψ.我们逻辑的满足性问题的一个朴素决策过程可以是:给定一个公式,构造所有Kripke模型,其中最多2 |ψ|状 态 ,验证它们是否属于适当的类,并测试是否他对他们的某种状态感到满意大约有22个|ψ|这样的模型。因此,该算法为我们逻辑的可满足性问题建立了一个双指数时间上界PDL的可满足性问题是EXPTIME完全的[5]。这为我们逻辑的可满足性问题产生了一个指数时间下界五、结论本文提出了一个新的语义PDL的基础上有限运行上下文,据我们所知,这是一个新的语义,开辟了新的可能性,不仅为PDL,但为其他模态逻辑以及。我们提出了一个公理化,并证明了它的可靠性,完备性和有限模型性质。主要结果是双相似程序和逻辑等价程序之间的等价性我们证明了关于有限PDL+类的完备性,并且复杂性应该与PDL相同PDL+开辟了研究PDL新变体的可能性,其中程序是来自某些进程代数的进程术语。文[3]提出了一种CCS程序的动态逻辑,主要的批评是缺乏双相似过程和逻辑等价程序之间的我们的新语义完全解决了这个问题。在[3]中,我们还提出了一种逻辑,它使用递归代替迭代。但是,为了保持可判定性,我们不得不限制递归方程的使用。在目前的工作中,我们使用迭代和有限运行,只处理终止程序。我们想用递归来扩展这项工作,并研究更具表达力的语义。未来工作的另一种可能性是建立PDL+可满足性问题的精确复杂性。由于PDL,我们已经有了EXPTIME硬度。我们怀疑它是EXPTIME完全的,如PDL,但我们想为可满足性问题提供一个EXPTIME算法M.R. F Benevides/理论计算机科学电子笔记305(2014)5191K1引用[1] J.A. Bergstra,A. Ponse和S.A. Smolka(编辑),Handbook of Process Algebra,Elsevier,2001年。[2] R. 线 性 时 间 分 支 时 间 谱 I : 具 体 的 、 顺 序 过 程 的 语 义 学 . 在 Handbook of Process Algebra ( J.A.Bergstra,A. Ponse和S.A. Smolka,eds.),第1章,第100页3-99,Elsevier,2001。[3] M. R. F. Benevides和L. M.谢克特CCS程序的命题动态逻辑。在Proceedings of the XV Workshop onLogic,Language,Information and Computation,Volume 5110 ofLNAI,pages 83Springer,2008.[4] P. Blackburn,M. de Rijke和Y.维尼玛模态逻辑计算机科学中的理论理论。剑桥大学出版社,2001年。[5] D. Harel和D. Kozen和J.蒂乌伦动态逻辑 麻省理工学院出版社,2000年。[6] M.大坝关于pi演算的过程等价的可判定性。Theoretical Computer Science,183(2):215[7] M. J. Fischer和R. E.拉德纳正则程序的命题动态逻辑。Journal of Computer and System Sciences,18(2):194-211,1979.[8] W. J. Fokkink 进程代数导论。理论计算机科学教科书。 施普林格,2000年。[9] D. Harel和D.拉兹非正规程序的决定性质。SIAM Journal on Computing,22(4):857[10] R.米尔纳 通信和并发。 普伦蒂斯·霍尔1989年[11] R.米尔纳 通信和移动系统:π-演算。 剑桥大学出版社,1999年。[12] R. Milner,J.Parrow和D.沃克移动过程的模态逻辑Theoretical Computer Science,114(1):149[13] D.法勒并发动态逻辑中的通信。Journal of Computer and System Sciences,35(1):23[14] D.法勒并发动态逻辑。Journal of the Association for Computing Machinery,34(2):450[15] C.斯特灵 过程的模态和时间特性。 计算机科学中的文本。施普林格,2001年。[16] R. 戈德布拉特时间与计算的逻辑第七章.斯坦福大学,1992年。引理的证明3.10是的。 我们通过归纳法给出了−→αc的长度n。• n=1,对某个作用量α,th e n−→αc=α{β1· · ·β1}。然后,π→−αc惠π→αc。根据这一论点,1k1⇒√ √απ→τ表明,{α,β1· · ·β1}是π和τ唯一能执行的作用,且π→α⇔τ→. 最后,τ→α惠τ→−αcτ。1k1•C1→C2I. H.:假设引理对所有n k成立。设α是一个长度为k的序列。设α{β1···βk1}为序列的第一个作用,设−→γc e是一个长度为k−1的序列,满足−→αc=α{β1· · ·β1}。−→γc。→−αc′α′′→−γc1k1α′然后,π当且仅当存在过程π使得π→π且π。 但如果π→π和ππτ,则存在一个过程τ ′,使得τ→ατ ′,π′→τ ′。更进一步地,当ππτ时,n{α,β1· · ·β1}是只有π和τ能起作用。Now,−→γc是一个长度短于k的序列,因此y是归纳法′→−γc′→−γc→−αc假设,如ππτ关于π,则τ. 这意味着,Q20M.R. F Benevides/理论计算机科学电子笔记305(2014)5F产品介绍FF≥M F MFFFF≥FFFFFFFFFFFB引理4.4的证明证据 我们用归纳法证明了π的结构。基本情况是|π| = 1,对于原子程序来说,这很简单。假设它适用于|π|所以我们有三种可能性。• 设M, wD<$π<$<$i<$i ∈Ws,则v∈Ws. t. wRπv和M, vDπ v。 但我们知道Rπ=Rπ。那么我们得到一条路径wRπv1Rπ. Rπv.AsRπ是Rπv和M, vD的过渡,但这是i,wDπ。通过归纳假设,有一条有限路径(v0,v1,...,vn),n 1,使得v0=w,vn=v,M,vnDn,且存在长度为n的−→αc∈−R→c(π)suc h,使得−→αc满足c是路(v0, . ,vn)。 但由定理3.13我们知道−R→c(π)<$(−R→c(π))<$=−R→c(π<$)π=π1+π2和π=π1;π2的情况与前面的情况类似。QC引理4.8的证明证据()假设,对于某个模型=(,V)和该模型中的某个状态w,,wDπ1+π2p. 然后,通过引理4.4,在w处匹配π1+π2,存在有限路径(v0,v1,.,vn),n 1,使得v0= w,M,vnDp,以及满足这条路的序列−→αc∈−R→c(π1+π2).N ow,by是定理3.1 3中的第三个等式y,e ith e r−→αc∈−R→c(π1)|+π2或−→αc∈R−→c(π2)|+π1,它跟随着f f根据定义3.12,−→αc|−π2∈−R→c(π1)or−→αc|−π1∈R−→c(π2)。此外,−→αc|−π2和−→αc|−π1mat chpath(v0,v1, . ,vn).,这意味着M, wD<$π1<$p或M,wDπ2p. 因此,M,wD <$π1<$p <$$>π2<$p(1)。−→当F在w处为π1+π2时,s oF在w处为π1和π2。 则存在−α→1c∈Rc(π1)使c是一条路(w0,v1, . ,wk)和−α→2c∈−R→c(π2),使得c是一条路(u0,v1, . ,u1)且w=w0=u0。这意味着M,wD<$π1<$T和M,wD<$π2<$T。因此,M,wD<$π1<$T <$$><$π2<$T(2)。从(1)和(2),我们有M,wD(<$π1<$p<$$>π2<$p)<$(<$π1<$T <$$>π2<$T)(1)设M,wD<$π1<$p<$$>π2<$p(1)和M,wD<$π1<$T<$$>π2<$T(2)。从(2)我们得到F在w处匹配π1和π2。由式(1),我们有M,wD<$π1<$p(3)或M,wD<$π2<$p(4)。(3)意味着在w处匹配π1,并且存在有限路径(v0,v1,..., vn),n1,使得v0= w,M,vnDp和一个序列−α→1c∈−R→c(π1),使c满足这条路.由于−α→1c∈−R→c(π1),所以−α→1c|+π2∈R−→c(π1)|+π2<$−R→c(π1)|+π2<$R−→c(π2)|+π1=R−→c(π1+π2)(使用定理3.13(3.))。因此,−α→1c|+π2∈−R→c(π1+π2)。由(2)可知:−α→1c|+π2表示路径(v0,v1, . ,vn)。我们,M,wD <$π1+π2 <$p.类似地,从(4)我们也得到M,wD<$π1+π2 <$p。QDPDL+的完备性证明规范模型构造是用于PDL的标准模型构造[5,4,16]。定义D.1(Fischer和Ladner闭包):设Γ是一组公式。 关于Γ的闭包,记法CFL(r)是满足以下条件的最小公式集:1. CFL(Γ)在子公式下是封闭的,2. 若<$π<$∈CFL(Γ),则<$π <$$><$π <$∈CFL(Γ),3. 若∈CF L(Γ),则π2∈CF L(Γ),4. 若∈CFL(Γ),则∈CFL(Γ),5. 若<$π1<$π2 <$$>∈CFL(Γ),则<$π1<$T和<$π2<$T∈CFL(Γ),6. 如果n∈CFL(Γ)且n不具有形式<$n,则<$n∈ CFL(Γ)。证明如果Γ是有限的公式集,则Γ的闭包CFL(Γ)也是有限的。 我们假设从现在开始我将永远是你的朋友。·M.R. F Benevides/理论计算机科学电子笔记305(2014)521一定义D.2设Γ是一组公式。 一个公式集称为Γ的一个原子,如果它是CFL(Γ)的一个极大相容子集. 所有原子的集合由At(Γ)表示。22M.R. F Benevides/理论计算机科学电子笔记305(2014)5πAS B i <$A <$$> π<$B是一致的。π∧∨ ∨ ∨ ∨∨||≤{A∈|∈A}是的。 我们可以按如下方式构造原子A。首先,我们把C_F_ L(r)的元素记为φ_1,· · ·,φ_n。► participate((Aα(φ)是一致的,或一个α(<$φ)是其中,一种新的生物技术,B)是一致的,根据定义D.4ASαB。一致 因此,通过适当地选择φ,对于所有公式φ∈CFL,我们可以构造一个原子B,使得C1···Cn)。不难看出,C[π]C→[π]C).使用SegerBerg公理(公理6),我们(π2B <$$>π1<$T))是一致的。要么(π2B <$$>π1<$T))是一致的(2)。A((π1B <$$>π2 <$T)是一致的(1)或设∈ A。 根据定义D.2,我们知道A α是相容的。使用同义反复不一致,因此不一致A→[π]C是一个定理。∧引理D.3设Γ是一组公式。如果<$∈ CFL(Γ)和<$是相容的,则存在原子A ∈At(Γ)使得λ∈ A。我们开始构造,使A1={n},然后对于1,其中对于所有命题符号p和所有原子A ∈ At(Γ),我们有- VΓ(p)={A ∈At(Γ)|p∈ A}称为典范赋值;- SΓ和SΓ+是典型关系。3ππ引理D.6设A ∈ At(Γ). 然 后 ,对于所有基本程序α,存在B ∈ At(Γ)使得ASαB和A ∈ B.证据假设存在B使得A∈ B且ASαB。 然后AαB是一致的,A也是一致的,是一致的. 但∈ CFL和极大性∈ A。Q引理D.7L∈A,B∈At(Γ). 如果ASπ <$B,则ASπ<$B。Pr oof. 辅助位置ASπB。 L e tC={C∈At(Γ)|ASπ<$C}。 我们要证明B∈C. LetC=A,Cπ D将是一致的,并且对于某些Ci,Ci<$$>π<$D也会支持,∧∨这意味着D ∈C,但事实并非如此 根据类似 的推理,我们知道, π也是由于C<$$><$<$π <$$> C<$是不一致的,所以它的否定是一个定理<$$>(C<$$><$<$π<$$>C<$),也是一个定理<$(C<$→► ([π]C→[π)和通过(1)得到了→[π). As A→[π]C是一个定理,则►A→[πι]Cπι。通过支持,AπB是consistent nt,BC也是consistentnt。因此,至少对于一个C ∈C,我们知道,对于C,我们有ASπ<$B。B组C是一致的。通过极大性,我们有B=C。而根据定义,Q定义D.8设Γ是一组公式。T上的PDL+模型是元组M= ∈ A且<$π2<$T∈A(5)或<$π 2<$$> ∈ A且<$π1<$T∈A(6)由(5)和(6)以及公理4.,我们知道Aπ1+ π2是相容的。通过极大化∈ AQ引理D.11真值引理:设M =(W,Sπ,V)是φ的有限正则模型。 对于所有原子A且所有的φ∈CFL(φ),M,A|=i∈ A.证据 :证明是通过归纳的结构。• 原子公式和布尔运算符:从V的定义中可以直接证明。• 对于x∈ { α,π 1 ; π 2,π 1 +π 2,π2},我们可以得到y ∈ x ∈ { α,π 1;π2,π1+π2,π 2}.• 假设M,A|=,则存在A′使得ASxA′,且M、A′| = A. 根据归纳假设,我们知道<$x∈ A
下载后可阅读完整内容,剩余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直接复制
信息提交成功