没有合适的资源?快使用搜索试试~ 我知道了~
过去是免费的:论具有过去的非线性时间属性尼古拉斯·马基1法国奥尔良大学基础信息学院6,rue Léonard de Vinci摘要本文研究了具有过去的线性时间逻辑(PLTL)的可满足性和模型检验的复杂性。更确切地说,我们认为几个片段的PLTL,根据允许的时间模态,使用否定或嵌套的未来公式到过去的公式。 我们的研究结果表明,“过去是免费的”,即它不会带来额外的理论复杂性,即使对于小的片段,甚至当将未来的公式嵌套到过去的公式中时。我们还注意到,存在和普遍的模型检查可以有不同的复杂性,某些片段。介绍时间逻辑。1977年,Pnueli [20]引入了时态逻辑来推理并发程序。这些逻辑提供了强有力的方法来指定和验证反应系统的属性。我们参考[3,5,18,19]以了解更多的动机和背景。研究中最常用的时态框架是线性时间命题时态逻辑(称为LTL)。一个LTL公式表达了所研究的系统中事件顺序的性质。例如,在任何时候,一项请求最终都会产生赠款,可以用以下方式表示G(申请联邦补助金)(S1)时间逻辑与过去LTL是纯未来时间逻辑,即模态仅涉及当前状态的未来的逻辑。然而,可以定义过去的时间1 电子邮件地址:markey@lifo.univ-orleans.fr2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。2US模式[10,8,16]。例如,为了表示只有在发出某个请求时才可能发生授权,我们可以写G(grant-1request)(S2)众所周知,自[10]以来,过去时间模态并不增加LTL的表达性。[7]给出了一种将LTL+Past公式转化为等价的纯未来LTL公式的方法。例如,(S2)的一个等价的纯未来公式是请求(S3)表示要么根本不授予,要么直到第一次请求才授予。由于关注极小性,因为它没有增加表达能力,过去没有被广泛研究,并且像Spin或Cadence-SMV这样的模型检查器不处理LTL+Past指定。已经提出了几种用于模型检查LTL+Past [23,11]的方法,但据我们所知,这些方法尚未实现。过去的好处允许过去时间模态使规范更容易,更自然(即更接近自然语言规范)[16]。 此外,在某种意义上,LTL+Past确实带来了更多的表达能力:[14]显示了LTL和LTL+Past之间的简洁性差距,即存在LTL+Past公式,只有指数大小的LTL最后,由于模型检查和可满足性对于LTL+Past来说并不困难(在两种情况下都是pspace完全的[22]),因此可以认为LTL+Past应该是首选。这些论点似乎表明,过去是免费的。能否使这一观察更有力、更系统?在本文中,我们调查,如果这个结果仍然适用于LTL+过去的不同片段,为了表征片段,更有表现力,但不是更难验证。我们的贡献。我们提供了一个系统的研究LTL+过去的片段获得三种限制:对一套允许的模态,使用否定,嵌套的过去和未来的模态。这些结果依赖于一些基本的技术,在整个文件中使用相关工作。关于LTL+Past的片段,[21]研究了LTL+Past的片段LusaT,仅具有和,并提供了最优(pspace)自动机理论算法。[4]研究了通过限制时态高度和原子命题个数得到的LTL文献[13,15]研究了具有过去的分支时间时态逻辑3--SU≡ TS ≡ ¬¬⇔T联系我们论文概要在续集中,我们首先正式定义所研究的结构,逻辑和问题,并总结我们的结果。在第二节中我们证明了np-完全性结果,在第三节中我们证明了p空间-完全性结果.我们总结了我们的研究,并在第4节结束。1PLTL:线性时态逻辑与过去PLTL的最大值设AP=P1,P2,.. . 是 一组可数的原子命题。 我们定义PLTL的语法如下:p LTL3 φ,n::= n φ |¬φ |Xφ |Uφ |X−1φ|公司简介|P1|P2|......这是什么?其中U表示一些非常有用的缩写通常被定义为:P1P1,、、、......至于时间模态,我们将使用经典的F和G,以及它们过去的对应物F−1φφ和G−1φF−1φ,分别读作模态X-1、F-1和G-1被称为 、X、F、G是语义pLTL的公式在路径上解释。路径是一对(π,π),其中π是状态π(0),π(1),.的无限序列。且π是从π (0),π(1),.,π(n),.. .2美联社。 这样,π的状态被标记为 原子命题给定一条路(π,π),一个自然i和一个公式φ,我们归纳地定义关系π,i|=φ(读作“φ保持在沿π的位置i“)如下:π,i|=P当且仅当P∈ π(i),π,i|当且仅当,π,i|=φ和π,i|=π,π,i|=<$φ当且仅当,π,i|= φ,π,i|= Xφ当且仅当,π,i+1|= φ,π,i |=<$U φ当且仅当存在某个j≥i s. t。π,j|= φ对于所有i≤k,0且π,i−1|= φ,π,i|=<$Sφ 当且仅当存在某个j≤i s. t。π,j|= φ且对所有j 0,使得对于nyintegernm,πn=πn+p. 因此,一条路径可以用一个循环来表示,这是一个最终周期的确定性Kripke结构。更精确地说,给定两个整数m和p >0,一个类型为(m,p)的循环是结构(Q,0,l,R),使得Q=<$0;m+p1)和R=(i,i+ 1)i <$0;m+ p2)(m+p1,m).一个循环就是一个有限结构,它 (m,p)类型的循环的大小是整数m+p。最终周期性路径的大小是对该路径进行编码的最小循环2.2.1对循环进行我们首先回顾以下结果:定理2.3给定一个纯未来公式φ和一个循环L,可以在时间O(|L|· |φ|)是否π L,0|= φ。在确定性KS上,cTL 模型检查算法可用于LTL公式也是如此,因为量化总是指唯一的执行。这种简单的方法并没有扩展到检查是否一个循环满足一个PLTL公式,因此是一个“有过去时间”的公式。事实上,在一个循环中,未来是确定的,而过去不是,即任何状态都有一个后继者,而状态在转移关系中有两个(甚至零个)前导者下面的引理给出了一种克服这个问题的方法。首先要记住的是,时间的高度(resp。future-temporal height,past-temporal height)是嵌套模态的最大数量(分别为未来模式、过去模式)。更一般地说,我们定义时间高度w.r.t. 一个或多个模态作为最大次数,9U|≤|≤||⇒|S|·≥ −≥||·−∈模态是嵌套的。我们用hO1,. On(φ).其次,h P(φ)表示φ的后期p口高,即hS,X−1(φ).引理2.4设φ为ak≥m+hP(φ)p,p LTL-公式。 对于任何类型为(m,p)的循环L,对于所有π L,k|=φi <$π L,k+p|= φ。粗略地说,这个引理表明,在一些初始的扰动之后,φ中的过去模态不能区分循环已经展开了多少次。证明证明是通过推导公式φ的结构:• 对于φ=P,φ=<$φ1和φ=φ1<$φ2,结果是明显的;• 如果φ=Xφ1或φ=φ1φ2,我们可以应用ind.hyp.到第k个之后的状态。这给出了结果。• 如果φ=X−1φ1,那么由于k−1≥m+(h P(φ1)+ 1)p−1≥m+h P(φ1)p,我们从归纳假设得到等价π L,k−1|=φ1惠π L,k − 1+ p |=φ1。 因此,π L,k |= X−1φ1惠π L,k + p |= X−1φ1;• 如果φ=φ1φ2,我们有hP(φ)= max(hP(φ1),hP(φ2))+1。设πL,k=φ. 存在着一些kJks. t。 πL,kJ=φ2,对于kJm+hP(φ)·p)加到S;如果n=X−1α,则将(j1,α)加到S上。我 们 知道,由于π L,j=X−1α。 故(1)仍然成立;如果f=Fα,我们知道α在某个状态k大于j且小于m+(h(φ)+1)p。如果k大于m+h(φ)p+1,那么我们可以对p进行次迭代,以保持小于m+h(φ)p+1(由于引理2.4)。因此,我们将(k,α)加到S上,使得(1)仍然满足;· 如果f=F−1α,则参数相同。这个过程显然结束了,因为S中公式的大小之和在每一步都在减少。此外,委员会认为,|联系我们| ≤ |φ|到最后现在考虑L的可接受的子循环Lj,它包含我们在ST中保持的状态。我们也可以添加一些其他的状态(这种结构与图1中所示的结构相同)。我们把函数s. t写成f。π LJ“f π L.前面的证明仍然适用。那么π LJ,f−1(i)|=φ。因此,我们证明了对于任何(j,n)∈T<$S,我们有π LJ,f−1(j)|=:显然,对于S中的每个(j,),我们有π LJ,f−1(j)|=,因为是原子命题。对于(j,n)∈T,可能会出现几种情况:• 如果n=α β,则(j,α)或(j,β)在TS中,结果由ind得出。hyper.,• 若α β=α β,则(j,α)和(j,β)都在TS中,其结果也来自于ind.hyper.,• 若n=Xα,则(j+ 1,α)(或(j+1 p,α))在T S中。在第一种情况下,结果是直接的。在第二种情况下,它来自引理2.4,• 对于其他模态F、F-1和X-1,论证是相同的Q引理2.11Letφ∈L+(G,S)是一个令人满意的公式,且Lalops. t. πL,0|=φ。·13Letπ0是πL的初态,且d(ak)k=0. i-1是i个状态的一个nys方程,对于任意的自然i。我们构建循环LJ=a0·a1···a i−1·(π0)ω。然后14||`阿姆斯壮n(i,j)∈[1,m−1]×[1,n],f(i,j)×--π LJ,i |= φ。这个引理确保了我们可以找到一个只有一个状态的见证人来证明所研究的满足公式(取i= 0)。证明证明是由结构归纳φ:• 这个结果显然适用于原子命题,也适用于较小公式的合取和析取;• 假设πL,0=G。 Let(ak)k=0.. i−1是fi个状态的序列。当然,πL,0 =π,通过归纳假设,对于任何整数j,我们可以建立循环L j= a0·a1···ai−1·π0···π0·(π0)ω。j次则π Lj,i + j|通过归纳,对于任何自然的j, 因此π LJ,i |= G• 如果π L,0|=<$1S<$2,则显然π L,0|=0.02。通过归纳,π LJ,i|=0.2,对于fi状态的n y s序列(ak)k=0. i−1。 很明显,这是πLJ, i的尾部|=0.1S0.2。定理2.12对于L(X,X−1,S),L(F,F−1),L+(F,F−1,X,X−1)以及它们的非平凡函数,可满足性和存在模型检验是np -完全的。 L+(G,S)及其非平凡函数的可满足性是n p -完全的.Np-容易性是前面结果的直接结果。np-硬度在2.1节中得到证明。3PSPACE完全问题在本节中,我们证明了pLTL的几个片段的验证问题的pspace-硬度。证明是从平铺问题减少。设C是一组有限的颜色。多米诺骨牌类型是一个4元组,由C的颜色组成,上、下、左、右分别为d、 d。给定一个多米诺骨牌类型的集合T<$C4,以及两个整数m和n,平铺m×n网格相当于找到一个函数f:[1,m]×[1,n]→Ts. t。权起来i =f(i+1,j)左下来<$(i,j)∈[1,m]×[1,n−1],f(i,j)=f(i,j+1)我们考虑下面的平铺问题,这是[9,prob.B2]:给定多米诺骨牌类型的集合T,自然m(一元),C的两种颜色c0和c1,是否存在自然ns.t.mn-网格可以平铺,附加条件是f(1,1)down=c0和f(m,n)up=c1?这个问题是pspace-complete的。令(C,T=d1,. dp,m,c0,c1)是B2的实例。W.l.o.g.,我们可以假设,其D向上颜色为c1的多米诺骨牌类型从1到q编号,而其他多米诺骨牌类型从q+1到p编号。我 们 构 建 了 图 2 所 示 的 Kripke 结 构 。 原 子 命 题 的 集 合 是T<${E}<${i=k|k= 1,.,m}。初始状态是那些Q15..···.······.······....Ei=2,d1i=1,d1i=2,d2i=1,d2i=2,dqi=1,dqi=2,dq+1i=1,dq+1i=2,dpi=1,dpi=m,d1i=m,d2i=m,dqi=m,dq+1i=m,dp≤ −UUd向 下颜色是c0,i的值是1。对于k,启用从标记为i=k的状态到标记为i=k+ 1的状态的所有转换M1.一、 为 i=m,如果d向上颜色不是c1,则仅可能进入标记为i= 1的状态,否则仅可能进入状态E。图2. 与我们的平铺问题相关联的Kripke结构K我们现在必须写出公式,• 颜色从左到右(φhoriz);• 颜色从上到下(φvert)。当路径最终到达E时,初始条件和最终条件都为真。3.1函数L+(U)[22]证明了模型检查和可满足性对于L()是p空间完全的。这里的结果稍微强一点,因为我们不能,例如,在L +(U)中编码Gmdaliy。Theorem3. 1.对L~+(U)的势模是一种有效的模。证明我们只需要用L+()来表示前面所述的三个性质公式:• 满足• 从左到右的颜色顺序是正确的:.m−1k=1d∈T(i=kd).i=kU(i=k+1)dJ∈TdJleft=drightΣΣ(D)联合王国16U×→∈uniq∈∈• 从下到上的顺序也是正确的.M(i=kd).i=kU.<$i=kk=1d∈T(<$i=k)U.E(i=kdJ∈TdJdown=dupΣΣΣΣ(D)联合王国满足这些公式的合取的K中的路径最终到达E,在已经运行n次通过i= 1的状态之后。这条路径以明显的方式产生函数f:[1,m] [1,n]T。这个函数是一个平铺函数,因为路径满足φhoriz和φvert条件。”(《易经》)完全)问题B2可(多项式)归结为L+(U)的模型,且L+(U)的模型是非常困难的。Q推论3.2L+(U)的可满足性是pspace-ha rd。证明这种证明的经典方法是将模型检查问题简化为满意问题。 然而,由于我们不能在L +()中使用或表示G,所以我们不能编码(一般)Kripke结构的行为。因此,我们将通过将图2的Kripke 结构编码为m ula 的L +(U),将我们的平铺问题简化为满足性问题。我们必须表示,在到达E之前,路径应该满足以下性质:• i在每个状态下只有一个值,d T也只有一个,除非我们在状态E;• 任何路径在i= 1状态下开始,其中ddown=c0;• i从1增加到m,然后回到1,除非dup=c1;• 我们只能从i=m状态进入E状态;我们定义2)A=A(10)A)A)B)C)ssJ)。第一个属性这样写s∈Ss∈SsJ∈Sz{s}φd=ef<$E惠(uni q({i=k} <$uni q(T)).第三和第四个属性可以通过以下方式表示m−1φincrd=efk=1(i=k(i=kUi=k+1))((i=m)d Tdup=c1d)(i=mU(E)((i=m)d T dup=c117d)(i=mUi= 1))18S简体中文S因此,全局约简可以写为:(i= 1<$ddown =c0)<$(φuniq<$φincr<$φvert<$φhoriz)UEQTheorem3. 3普适模型是对L~+(U)的一种普适模型。这个证明考虑了一个稍微修改过的平铺问题:输入是相同的,但问题是是否所有正确的平铺都将c0作为最左边的底部颜色,最终将c1作为最右边的顶部颜色。由于pspace和co-pspace重合,这个问题显然是pspace完备的.我们将编写一个公式,表示每条路径要么不代表正确的切片,要么最终到达E状态。我们这样写φhorizd=efm−1k=1d∈TTU(i=kd(i=kU(i=k+1dJ∈TdJleft=dright<$dJ))φvertMd=efTU(i=kd(i=kU(<$i=kk=1d∈T(<$i=kU(i=kdJ∈TdJdown=dup<$dJ)满足这些属性的路径并不对应于正确的平铺。因此,检查所有路径是否满足φ horizφ vertE等于解决了我们的平铺问题。Q3.2对L+(F,X),L+(G,X)和L+(G,X−1)的psp-均匀性[22]证明了L+(F,X)的满足性和存在性模型是np-完备的.我们在这里表明,通用模型检查是更难的片段。Theorem3. 4.对L+(F,X)的普适模型进行了研究。证明约简与前一个相似,公式更容易编写。Q通过对偶性,我们得到推论3.5潜在的模型检查和满足性是pspace-hard的。L+(G,X).对于存在性模型检验,结果来自于前面定理的对偶性。这在[4]中已得到证实。在[22]中给出了从存在性模型检验到L(F,X)的可满足性的一个约化,并且该约化也适用于L+(G,X)。QTheorem3. 6L+(G,X−1)a的概率模型和可pspace-hard.19∧ ∧¬SSSSSSSSSS对于存在性模型检验,我们考虑一个问题的对偶问题, 我们用于定理3.3的证明:给定相同的输入,问题是是否存在永远不满足“最终”条件的正确平铺。为此,我们只需写所考虑的路径满足平铺条件:φhorizMd=efG(i=kdX−1dJ)k=2d∈TdJ∈TdJright=dleftφvertMd=efG(i=kd(X−1kX−1ndJ))k=1d∈TdJ∈TdJup=ddown检查是否存在一条满足φhoriz φvertGE的路径就等于解决了初始的pspace-hard问题。[22]中给出的从存在性模型检验到满足性的简化对于L(F,X)可以很容易地适应f或L+(G,X−1)。Q3.3L~+(F,S)和L~+(G,S)的psP性Theorem3. 7.对L+(F,S)和L+(G,S)的建模是并行的。是个-S s可解性是pspace-ha rdf或L+(F,S)。这些证明与前面的证明非常相似• 对于L ~+(F,S)和L~+(G,S)的现有模型,在L+(U)的现有基本模型中几乎是相同的;• 为了满足要求,我们简单地将图2的结构编码为L+(F,S)公式;• 对于通用模型检查,约简类似于The-orem 3.3中的约简。QTheorem3. 图8F+(U)的建模和满意度问题,L+(G,X),L+(G,X−1),L+(F,S),并且对于pLTl的函数包含以下之一:他们,一个repspace-ccomplete. 对L+(G,S)的建模是完全的。这是[22,定理4.1]和本节定理的直接结果。Q4总结发言我们得到的结果是足够的,完全分类所有考虑的碎片的pltlw.r.t.(存在的和普遍的)模型检查和可满足性问题的复杂性。这个详尽的案例研究导致了几个令人惊讶的结果。我们证明了存在性和通用模型检查对于正片段(npvs.pspace)可能具有不同的复杂性。我们只发现了一种情况,存在模型检查和满足性具有不同的理论复杂性。上20另一方面,我们观察到,使用所允许的未来模态的对称过去模态不会增加验证问题的复杂性在过去模式的范围内使用未来模式也是如此。这一切都归结为一个结论,即过去真的很便宜。通过对LTL片段中加入past的效果进行研究,有趣的是,度量时态逻辑来自[12],但不是[1]的时间命题时态逻辑)。引用[1] 巴尔河和T. A. Henzinger,A really temporal logic,in:Proc.30th IEEE Symp.计算机科学的基础(FOCS'89),研究三角公园,NC,美国,1989年10月,1989年,第11页。164-169.[2] 巴尔河和T. A. Henzinger,Real-time logics:Complexity and expressiveness,Information and Computation104(1993),pp. 35比77[3] Clarke,E. M.,O. Grumberg和D. A. Peled,[4] Demri,S. Schnoebelen,The Complexity of Propositional Linear Temporal Logicsin Simple Cases,Information and Computation174(2002),pp.84比103网址http://www.lsv.ens-cachan.fr/Publis/PAPERS/DS-ICOMP2001.ps[5] Emerson,E.一、时间和模态逻辑,在:J。诉Leeuwen,编辑,理论计算机科学手册,卷。 B,Elsevier Science,1990 pp. 995-1072[6] Etessami,K.,M. Y. Vardi和T. Wilke,First Order Logic with Two Variables(一阶双变量逻辑)和一元时序逻辑,在:Proc.12th IEEE Symp. Logic inComputer Science(LICS'97),Warsaw,Poland,June-July 1997(1997),pp. 228-235[7] Gabbay,D. M.,陈述式过去和命令式未来:交互式系统的可执行时态逻辑,在:Proc. Workshop
下载后可阅读完整内容,剩余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直接复制
信息提交成功