没有合适的资源?快使用搜索试试~ 我知道了~
BCTL全计算树逻辑的根tableau技术的性能优化
可在www.sciencedirect.com在线获取理论计算机科学电子笔记278(2011)145-158www.elsevier.com/locate/entcsBCTL的扎根Tableau约翰·克里斯托弗计算机科学与软件工程西澳大学澳大利亚珀斯摘要现有的用于满足性检查BCTL* [7]的纯tableau技术开始于构造所有可能的颜色。传统的表格从单个根节点开始,并且仅构造从该根导出的公式。这些有根tableaux在大多数真实世界的公式上提供了更好的性能,因为它们只需要构造一小部分可能的节点。 我们为BCTL* 提供了此表的一个有根变体,以及一个演示有根变体性能的实现优于原来的;这个实现是作为Java applet提供的。我们将讨论进一步的优化。这项研究将有助于为CTL* 找到一个优化的根表关键词:完整计算树逻辑,BCTL*,Tableau,捆绑。1引言最近,人们对全计算树逻辑(CTL*)的决策过程重新产生了兴趣人们早就知道CTL* 是可判定的,并且是2 EXP- TIME完全的,[1,2]提供了一个基于双指数自动机的满足性检查器,[9]给出了一个下界。基于自动机的满意度检查器预计平均性能较差,尚未实现[3]。最近,已经提出了基于tableau的决策过程,这些决策过程具有更大的合理现实世界性能潜力,并且具有公开访问的实现[8,3]。[8]的CTL* 表建立在捆绑全计算树逻辑(BCTL*)[7]的先前表的基础上。BCTL* 是CTL* 的变体,它具有相同的语法,但其中只有路径在一定的束中被考虑。 由于bundle可以包含所有路径,因此如果公式在CTL* 中满足,在BCTL* 中也满足。 同样,如果它是一个定理,它也是BCTL* 的一个定理,因此在可能的情况下证明公式是BCTL* 的一个定理是合理的,因此我们可以使用该定理而不需要1电子邮件:john@csse.uwa.edu.au1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2011.10.012146J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145V∧ ∧¬V→ ∧→考虑BCTL* 和CTL* 之间的差异。此外,我们注意到,当只考虑有限的时间段时,捆绑和非捆绑语义是等价的(例如参见[5])。CTL* 和BCTL* 的比较见第2.4传统的tableau从一个公式开始,然后构建一棵树,标签以该公式为根。在[7]中定义的tableau改为从最大tableau开始,然后修剪节点。这足以给出最坏情况下的最优性能结果;然而,这意味着我们必须始终构造所有可能的节点。因此,对于[7]的表,检查φ p p的满足性比检查φ p的满足性要花更长的时间。相比之下,一个扎根的场景通常会很快找到矛盾并终止。虽然[3]的CTL* 的混合满足性检查器总体上似乎比[8]更快,但我们出于三个原因调查了查找有根表首先,[8]的表可以很快,例如,使用默认设置,[8]的表显示(p(qUr))(qUp))(qUr)在0.16秒内是满意的,而在同一个Core2Duo上单独构建[3因此,有必要研究[7]和[8]的表格的改进,以确定它们是否能够超越[3]。其次,由于[3]是基于一个有根的画面,比较[3]和[8]的一个有根变体更有意义。第三,[7]和[8]的方法通过构建由用户输入的公式的子公式构建的有限表来工作,每个步骤都基于(B)CTL* 的语义。这些场景的工作方式对用户来说比[3]的工作方式更有意义,[3]的工作方式是使用奇偶博弈来解释无限场景的存在。本文提出了文[7]中 BCTL表的一个带根变式2虽然BCTL* 比CTL* 有一些优势,但我们选择实现BCTL* 表的主要原因是[8]的CTL* 表是从[7]的更简单的BCTL* 表构建的。因此,在尝试优化相应的CTL* 表之前,研究和优化更简单的BCTL*表2BCTL* 逻辑2.1BCTL *与CTL* 一样,BCTL* 具有一组我们称之为原子的原子命题。 当p变化时,我们根据以下抽象语法φ:= T|p |¬φ|(φ φ)|(φUφ)|Xφ |Aφ。T、<$、X、U和A是CTL和CTL* 中常见的“true”、“not”、“and”、“next”、“until”和“all paths”运算符。缩略语、、F、G、W、E→和Participate的定义与CTL* 逻辑相同,即:(p<$p),T <$,[2]这可以http://www.csse.uwa.edu.au/~john/BCTL2/以Java Applet的形式获得,并包括[7]和[8]的表格以供比较。J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145147∈V∈∈∈ ⟨ ⟩ ∈⟨⟩⟨⟩⟨⟩α<$β<$$>(<$α<$$> β),2.2CTL-结构定义2.1我们说S上的二元关系R是串行(全)的,如果对于每个a在S中存在b,使得aRb。我们有时会把aRb写成(a,b)∈R。定义2.2一个转移框架是一个对(W,>),其中W是一个非空的状态集,>是W上的一个序列关系。定义2.3我们让原子成为我们的集合。 赋值g是从一组态W到原子幂集的映射。非正式地,陈述p g(w)意味着定义2.4我们称一个nω-序列σ=ωw0 , w1 , . 。 。对于所有非可扩展类型i,i=wi>wi+1,对于N中的所有i,我们定义σ≥i为全路wi,wi+1, . 。 。 ,w e定义σi为b e wi,w e定义σ≤i为序列w0,w1, . 。 ,wi. 证明了一个全路集B对所有非线性范畴i,j和σ,π是闭闭集Bw e haveσ0,σ1, . ,σi,πj,πj+1, . 。 。B若σi +1=πj。我们说一个全路集B对所有的整数i和σ B都是sux闭的,我们有σ≥iB。 我们说一个全路径集合是一个丛,如果它是非空的,sunix闭的和fusion闭的。定义2.5BCTL结构M=(W,>,g,B)是一个包含状态集合W、串行二元关系>、状态集合W上的赋值g的4元组,B是(W,>)上的丛。2.3BCTL* 语义我们定义 了全路σ=w0,w1, . 上 的 m u l a φ 的 B C T L * 的 真 值 . 。 。在BCTL结构M中M,σ<$Xφi <$M,σ≥1<$φM,σ <$φU <$i <$<$i ∈Ns.t. M,σ≥i<且M,σ π ∈ Bs. t. π0=σ0M,πφp、<$和的定义正如我们从经典逻辑中所期望的那样M,σ<$pi <$p∈g(p0)M,σ<$i<$M,σ$φM,σφiM,σφM,σ,如果存在一个BCTL结构M=(W,>,g,B),则我们说公式φ在BCTL*中是可满足的,即在B中存在一个部分σ,使得M,σ∈φ. 一个公式是有效的,如果它的否定是不满足的。CTL* 类似,但B必须是通过>的所有可能路径的集合。148J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145→→→≤¬ ∈∈2.4CTL*在本文中,我们不会正式考虑CTL*;但是,我们将在这里简要讨论它,以便我们可以将其与BCTL* 进行比较。我们看到,如果一个公式在CTL* 中是可满足的,那么它在BCTL*中 一定是可满足的;等价地,如果它在BCTL*中 有效,那么它在CTL* 中一定是有效的。CTL* [6]的公理化包括极限闭包(LC)公理,这在BCTL中无效:LC:AG(Eα→EX((EβUEα))→(Eα→EG((EβUEα)考虑一个系统,其中我们处理有限但无限大小的非空输入。由于输入的大小是无限的,如果我们刚刚读取了一个输入符号,那么有可能我们将在下一步读取另一个输入符号,我们可能希望将其表示为r EXr;这将始终是真的,因为无论我们读取了多少输入符号,始终可能还有一个输入符号,我们可以将其表示为AG(rEXr),在CTL* 下,我们可以推断出rEGr. 以来input是非空的,我们有r,因此有EGr;这表明存在一个计算路径,我们永远读取新的输入符号。然而,我们已经说过,输入总是有限的。我们看到CTL* 的语义不适合于这个规格。首先尝试证明一个公式在BCTL* 中有效是合理的,如果它在BCTL*中 无效,只需要担心BCTL* 或CTL* 的语义是否更合适3适用于BCTL的Tableau *在这里,我们定义了一个表BCTL*-RTAB,用于检查BCTL* 公式的满足性。此表源自Reynolds定义3.1对于任何一对公式(φ,φ),我们说φ ∈ i φ φ是φ的子公式。定义3.2公式φ的闭包clφ被定义为满足以下四个要求的最小集合:(i) φ∈clφ(ii) 对于所有的ε∈clφ,如果δ≤ε,则δ∈clφ。(iii) 对所有的ε∈clφ,<$ε∈clφ或存在δ使得ε=<$δ且δ∈clφ。定义3.3我们说一个函数φ是部分命题相容的(PPC)i对于所有α,β∈clφ:(M1)如果α∈a则α∈a,(M2)如果(α<$β)∈a,则α∈a和β∈a。PPC集合与最大命题一致(MPC)集合非常相似,但MPC集合M1更强:如果β=α然后βa i a/ a。 关于MPC集合a,对于闭包中的每个公式α,a要么有α,要么有它的否定。相比之下J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145149¬PPC背后的直觉是PPC集合a可以排除α和α,除非其中一个公式是a中其他公式的直接结果。粗略地说,一个色调是一组公式,可以沿着一个完整的路径。定义3.4[色调]如果a满足H1、H3和H4(见下文),则集合aaclφ是φ的色调。一个集合a_i__φ是一个完成的色调,φ_i_i_i满足以下所有(H1)a为PPC;(H2)如 果 αUβ∈a , 则 α∈a 或 β∈a;( H3 ) 如 果 <$ ( αUβ ) ∈a , 则 <$β∈a;(H4)如果Aα∈a,则α∈a。[7]的色调类似于完成的色调,除了它们必须是MPC(不仅仅是PPC)。我们在色彩的定义中不包括H2,因此以下定义是唯一的:定义3.5对于一组公式a,我们让hue(a)是a的最小超集这也是一种色调。定义3.6其中h是一个完成的色调,我们定义succ(a)作为最小集合,使得(i) 如果Xα∈a,则α∈succ(a);(ii) 如果<$β∈a且αUβ∈a,则αUβ∈succ(a);(iii) 若<$(αUβ)∈a且α∈a,则<$(αUβ)∈succ(a).定义3.7[rA]对于色调a,b,我们将(a,b)放在rA中,如果以下条件成立:(A1)Aα∈ai <$Aα∈b(A2)对于所有p∈ V,我们有p∈ai <$p∈b定义3.8我们说一个色调集合C是一种颜色,如果它满足C1。一套色调C是φi的最终颜色,它满足:(C1)对于所有的a,b∈C,我们有(a,b)∈rA;(C2)如果a∈C且<$Aα∈a,则存在b∈C使得<$α∈b;我们现在定义一个函数Col;给定一组公式,集合Col(C)直观上是C的超集的最小颜色;然而,我们还没有定义集合的最小集合,所以我们正式定义Col如下:定义3.9对于公式C的集合的集合,集合(C)是当我们迭代时得到的集合:(i) 将C的每个成员a替换为色调(a);(ii) 将C中的每个成员a替换为a{α},其中α∈b∈C,且α具有以下形式Aβ、<$Aβ、p或<$p。150J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145表示式A((h))ΔE(h)。我我我¬。Σ∅∈联系我们∈ ∈∈(iii) 重复1和2,直到不可能再修改C所有的tableau规则都使用上面的定义来确保每个节点都是一种颜色。这增加了这个画面与[7]的相似性(其中所有节点都是颜色)。与[7]一样,色调a表示公式a,并且C={h1,h2,...,hn} rep-在画面中,我们允许色调包含特殊标记e。这表明我们已经选择了这个色调作为我们将尝试寻找时间继任者的色调。我们将始终在每种颜色的一种色调中得到e对于颜色C,我们设Ce为C中包含e的色调。包含e的色调类似于论文[8]中的第一个色调h0,顺便说一下,这也是我们在示例实现中实现e定义3.10对于下面形式之一的每个公式,我们定义左选择L(L)和右选择R(R)如下:ψL()R(N)<$(α<$β)¬α¬β(αUβ)β¬β<$(αUβ)¬αα注意,下面两个规则是必需的,因为(与[7]一样)我们没有将X(αUβ)添加到闭包集合中,所以我们使用公式β和(αUβ)来指示时间后继者也必须包含αUβ。规则节点是元组(C,一个元组(C,节点是规则节点或时间节点。每个节点都与一个分支相关联。每个分支都有一个字母来表示分支的类型,一个节点是一个规则节点,除非它是H分支的子节点(定义如下)。我们从一个节点((φ,e,), 我们需要包括空色调,否则初始颜色将表示所有路径满足φ的情况,这可能不是这种情况。然后,我们如下迭代地定义表:对于每个规则节点(C,“R“),其中C = h 1,h 2,.,H|C|我们将一个分支定义如下,(i) 如果存在HC对于某个叶,使得L(λ)被定义为L(λ)/ h,R(R)/ h然后我们让(C,(a) 一个子元素((C1),“R“),其中C1是由C中的h加上L()得到的(b) 一个子元素((C2)R,(c)一个子节点((C3)<$,(d)子元素((C4)<$,(ii) 如果存在s<$A <$∈a∈C,则令(C,“R“)的分支是析取E-分支,|C|孩子们:J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145151| |∈--∈∈(a) 第i个孩子是((Ci),(iii) 如果我们不能应用规则1或规则2,那么我们让(C,(a) 第i个孩子是(Ci,移动到第i色调(给定色调的任意排序)。设(Ci,“R“)的分支是一个析取X-分支,|Ci|-1名子女。(Ci,“R“)的每个子元素直觉,(i)是关于完成色调,(ii)是关于完成颜色,(iii)是为了采取时间步骤,在全路径上移动到下一个世界定义3.11我们将颜色中的可能性集合定义为形式为αUβ的公式集合,使得αUβCe。我们定义一个节点(C,我们将可能性后代(eDescendants)定义为eChildren的传递闭包。 我们说C的一个可能性αUβ如果β∈Ce,则直接满足。我们说一个可能性在一个节点上是满足的,如果存在一个节点的e后裔,其中β∈Ce。如果一个析取分支的任何子分支没有被修剪,我们就说它被覆盖了。我们说一个连接分支被覆盖,如果它的所有孩子都没有被修剪。我们将一个分支标记为修剪,如果:(i) 分支的颜色C是矛盾的,即{,}h∈C;或(ii) 该分行不受保障;或(iii) 有一个令人不满意的结局。我们说,如果它停止,根不修剪的画面成功3.1可靠性和完备性BCTL*-RTAB是可靠的,也就是说,如果它在φ上停止并成功,那么φ在BCTL* 中是满意的我们在这里给出了一个证明,更多细节见[4]。假设BCTL*-RTAB用颜色集合Sj来完成。然后我们定义一个BCTL-结构M=(W,>,g,B)如下:W的集合是H-分支中使用的颜色的集合。我们把一对颜色(C,D)放在>i中(如果我们可以通过恰好穿过一个X分支从表中的(C,“R“)到达节点(D,“R“));世界/颜色C的赋值g(C)包含一个原子p ip C。我们现在定义捆绑路径B的集合。定义3.12[rX]下面关于色调的时间后继rX关系如[7]中所定义;对于rXi中的所有色调a,bput(a,b),满足以下条件:(R1)Xα∈a蕴涵α∈b152J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145∈(R2)<$Xα∈a蕴涵<$α∈b(R3)αUβ∈a和β∈/a蕴涵αUβ∈b(R4)<$(αUβ)∈a和α∈a蕴涵<$(αUβ)∈b引理3.13对于每个(C,D)∈>,我们有CerXDe,对于每个b∈D,我们有a∈C使得arXb.注意,X分支用succ(a)替换每个色调a;a是一个完成的色调,因此(a,succ(a))rX; X分支是唯一从色调中删除公式的分支,并且当从C到D旅行时,我们只穿过一个X分支,对于(C,D)∈>。由此很容易证明这个引理3.13。定义3.14我们称一个ω-序列<$(c0,h0),(c1,h1),. 。穿过W的对所有i≥0的i ∈ X:ea chci∈SJ,ea chhi∈ci,ea ch(ci,ci+1)∈>,ea ch(hi,hi+1)∈rX.我们说,这是一个完整的填充线程i,对于所有i≥0(i)对于hi中形式为(αUβ)的所有公式,存在j≥i使得β∈hj我们引入了一个全路σ = αc0,c1,. 。在B中,存在一个填充线程n(c0,h0),(c1,h1),.. 。我们说这条线证明σ在B中。命题3.15如果μ = π(c0,h0),(c1,h1),.。如果σ∈B,则对所有j≥0,μ≥ j则σ≥ j ∈ B。引理3.16B是fusion闭的假设σ,π在B中,且σ0=π1。我们将在下面展示,σπ0,σ0,σ1,.。∈B.一般情况下,σ0=πj由前缀闭包和归纳法得出。当σ ∈ B时,存在一个填充线μ = μ(σ0,h1),(σ1,h2),. 。- 是的当(π0,π1)∈>时,我们可以从π0中选择h0,使得(h0,h1)∈rX(见引理3.13)。若αUβ∈h0,则β∈h0或αUβ∈h1.当μ充满时,若αUβ∈h1,则存在j≥1使得β∈hj.引理3.17如果h∈c ∈SJ,则存在填充线程μ= μ(c0,h0),(c1,h1),. 。⟩使得h0=h和c0=c。 因此,σ= αc0,c1,c2,.。∈B.与Reynolds [7]一样,我们首先迭代地满足最古老的可能性。每一种可能性最终都会被填满。假设我们已经选择了μ的前n个元素,并且0≤i≤n。我们说,对于m u β ∈ / hj,对于所有j≤i ≤n,一个even n u α U β ∈hi是不 完全 的。对于最小i,使得在hi中存在未实现的可能性,我们实现该可能性如下:情形1:若不存在suchi,我们选择(cn,cn+1)such(cn,cn+1)∈>且(hn,hn+1)∈rX.J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145153∈∈⟨ ⟩ ⟨ ⟩∈--我我情形2:如果可能性的形式为αUβ,则必然存在αUβ hn。由于删除未填充可能性的修剪规则,对于某些j,必须存在一个实例序列(cn,hn,α Uβ),(cn+1,hn+1,α Uβ), . ,(cj,hj,αUβ)使得最后一个实例被直接填充(β hj),并且每个其他实例被链中的下一个实例填充。现在选择μ直到(cj,hj),β∈hj,则最终事件αUβ∈hi现在被满足。引理3.18对于clφ中的所有α,对于所有线程μ = n(c0,h0),(c1,h1),. 。辩护σ = σ c0,c1,.。我们有M,σ<$α如果α∈h0我们可以用归纳法证明这一点。设L为语句:对于所有线程μ=(c0,h0),(c1,h1), . 。 。 证明了σ=c0,c1, . 。 。 we have(W,>,g,B), σih0.首先注意,当λ是一个原子时,根据定义,Lλ 假设Lφ对cl φ中的所有φ成立,其中|ψ| ≤n。我们可以证明[4],对于cl φ中的任何ε,|ψ| ≤n+ 1。例如,假设α是α<$β的形式。 由于色调是PPC,我们看到α和β也在h0中。则M,σ<$α和M,σ<$β。因此M,σ<$α<$β。可靠性由引理3.17和3.18推出。完整性引理3.19画面将停止,在最坏的时间量双指数的输入公式的长度。闭包集在输入公式的长度上是线性的。我们看到,色调的数量是闭包集大小的单指数,颜色的数量是色调数量的指数我们只对规则节点应用规则,并且每种每一步在最坏的情况下是颜色数量的多项式,或者是色调数量的单指数。因此,BCTL*- RTAB将在最坏的情况下在公式长度上的双指数时间量内停止。定义3.20对于颜色C=h0,h1,...,hn 在表中,我们定义f(C)如下所示f(C) =.是的。A((hi))E. 你好。引理3.21 BCTL*-RTAB是完备的,也就是说,如果φ在BCTL* 中是可满足的,那么BCTL*-RTAB在φ上停止并成功。证明[4]涉及到显示颜色为C的节点永远不会被修剪 如果f(C)满足154J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145≥4性能我们已经构建了这个表的一个示例实现一旦构造了足够多的节点后代以知道是否将修剪节点,此我们在表1和表2中列出了结果列表。 表1基于一个类表中α1=AF Gq ,β1=AFAGq,对eachi1我们有αi+1=AFG αi和βi+1=AFAGβi。表2给出了[7]和[8]中使用的标准示例。在每一列中,第一个子列用于我们的新BCTL*表,第二子列用于[7]的旧BCTL* 表,第三个子列用于[3]的混合技术。 如果该技术成功完成,则“Sat”将为“Y”(或“N”),以指示该技术报告该公式(不)令人满意;“m”指示该过程超过1GB并失败,“h”指示超出了实现中的硬编码限制,“t”指示我们在一小时后简单地终止了该过程。“CPU时间”列是在具有2620M Core i7处理器和8GB RAM的计算机上实现所使用的秒数。新tableau中的颜色数量是规则节点中使用的唯一颜色的数量(注意,规则节点往往比时间节点多得多,每个时间节点都是规则节点的直接后代)。为了实现[3],我们让“颜色”是奇偶博弈中的状态数。我们在[3]中没有定义与色调等价的东西,所以没有第三个色调列。任何一列中的我们新的带根BCTL* 画面的性能优于原始画面。在表2中,我们可以看到Reynolds使用的每个示例公式都可以由我们的工作表处理,而许多公式无法由原始工作表处理(两者都使用默认设置)。 在每个表中,我们看到新的tableau可以处理原始表可以处理的所有公式,而且我们的新tableau通常要快得多,而且从来没有明显慢过。与[3]的比较是初步的。注意,[3]技术是针对CTL* 的,而out技术是针对BCTL* 的,因此比较实现的运行时间可能会产生误导。如果[3]的运行时间用“*”标记,则[ 3 ]的技术已经证明该公式在CTL*(因此BCTL*)中也是满意的如果运行时间标记为“L”,则公式是LTL公式,即它不包含任何路径量化器(A / E),因此它在CTL*中是满意的,如果它在BCTL* 中是满意的如果它被标记为“N”,那么正如我们已经证明的,它在BCTL* 中是不满足的,因此在CTL* 中也是不满足的,我们已经证明了一个更强的结果。考虑到这个tableau的[8]样式变体需要复制颜色,我们认为BCTL* 比CTL* 更容易,因此我们认为比较用“N”标记的运行时间执行[3] 需要一个奇偶性博弈求解器,但默认情况下不选择我们选择了在我们的基准测试中,我们发现[3]的实现在奇偶博弈求解器中花费的时间不到十分之一,因此研究这些基准的其他求解器没有什么意义。 为了骗-J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145155¬¬¬¬¬{}联系我们尽管如此,我们将纯表格的堆大小限制为1GB;对于[3]提供的实现,我们无法做到这一点;然而,我们使用的是32位架构,因此我们怀疑他们的实现可能会使用超过一个数量级的内存。在我们的基准中,[3]的表现比[3]提供的基准差得多我们认为这是因为我们使用了32位架构。我们的直觉是,我们的技术通常能够比[3]更快地证明一个公式是可满足的,但要找到一个[3]无法推理的简短公式会更困难。我们的纯tableau技术可以在找到输入公式的模型后立即退出。这为我们的技术提供了作为一个令人满意的公式,一个显著的优点是可以由许多不同的模型来满足。相比之下,[3]技术总是完成一个平价博弈。然而,一旦奇偶博弈完成,许多经过充分研究的奇偶博弈解决技术都可以使用,因此有理由相信很难找到一个相对较短的定理,不能被证明[3]。虽然严格比较这些技术还为时过早,但我们的基准测试至少与这种直觉兼容。有很多可能的优化。(i) [7]的实现首先计算与LTL语义我们可以类似地要求颜色只包含LTL一致的色调。对于这种优化的基准测试,请参见[4]。(ii) 如果a、h、bC和H那么我们可以通过从C中去掉h来简化C。 为了证明这是安全的,请注意,这并不是一个严格的f(C)。(iii) 实现盲目地添加eDescendants试图填充可能性,然后覆盖它们。如果它只覆盖分支上的eDescendants,那就更快了。(iv) 像[7]一样,我们使用β和αUβ来表示时间后继必须包含αUβ。这意味着β及其子公式既可以是正的也可以是负的,从而可能使闭包集的大小加倍。使用X(αUβ)可能更有效。(v) X分支有指数数量的子分支。我们可以改变X分支,使它们只有一个孩子,通过包括所有的色调,但标记的色调,不下降,从Ce作为可选的,我们改变H分支,使他们只选择非可选的色调。当在一个可选的色调中发现矛盾时,我们从颜色中删除色调,而不是修剪颜色。当一个可选的色调包含一个形式为Aβ,Aβ,p或p的公式,而这个公式在C的其他色调中不存在时,我们就不总是把A β加到所有其他色调上,而是加一个分支,沿着这个分支我们可以去掉可选的色调。有许多理由相信这会更有效:在我们需要分支之前,我们可能会遇到一个矛盾;分支的数量至多等于Aβ,Aβ,p或p形式的公式的数量;可能所有的色调都已经有了分支,在这种情况下,我们可以完全避免分支。156J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145图1. 示例输出:证明Xp → Fp>/.输入内部节点/输入不可满足的叶N/Y退出节点(不满足)/退出节点(满足)L叶形式<$(αUβ)公式X临时后继分支,也是:下一次操作符XH选择色调分支(将所选色调移动到h0)C:节点的颜色P:节点的父节点D:节点的子节点S:一系列可能性o/c/e原始节点/创建节点以覆盖父节点/解决可能性-& -|/>否定<$/和()/或()/蕴涵(→)表1渐近基准q→ qβ1→AFGqβ2→α2β3→α3β4→α4!!!!“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天!“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天“”我的天!!!!!!!“““““““““““““““““““““““““!!“““““““““““““β5→α5β6→α6β7→α7β8→α8β9→α9β10→α 10β11→α 11β12→α 12β13→α 13β14→α 14β15→α 15<$(q→q)<$(AFGq→β1)<$(α2→β2)<$(α 3 → β3)<$(α4→β4)###!“”我的天“”我的天!!“”我的天!““““!““<$(q→q)<$(β1→AFGq)<$(β2→α2)<$(β3→α3)<$(β4→α4)我的天第一百一十二章我的天啊“”我的天!“”我的天“”我的天##!“!“““!“““J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145157¬联系我们(a) 如果a,h,C和ah和h是可选的,我们可以简化C,H.(类似于上面的(1))。(b) 如果(c) 我们不能总是构造可选择的色调,而只能在需要它们的时候才构造它们,因为我们遇到了形式为<$Aα的公式。158J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145表2.基准G(p→q)→(Gp→Gq)<$(G(p→q)→(Gp→Gq))Gp→(p<$Xp<$XGp)<$(Gp→(p<$Xp<$XGp))(pUq)参与(q<$(p<$X(pUq)<$((pUq)Participate(q<$(p<$X(pUq)(pUq)→Fq<$((pUq)→Fq)p→AEp<$(p→AEp)Ap→AAp<$(Ap→AAp)AXp→XAp<$(AXp→XAp)p→Ap<$(p→Ap)E(pU(E(pUq)))→E(pUq)<$(E(pU(E(pUq)→E(pUq))(AG(p→(qUr))(qUp))→(qUr)<$((AG(p→(qUr))(qUp))→(qUr))G(EFp→XFEFp)→(EFp→GFEFp)<$(G(EFp→XFEFp)→(EFp→GFEFp))AG(p→EXp)→(p→EGp)<$(AG(p→EXp)→(p→EGp))AG(Ep→EX((Eq)U(Ep))→(Ep→EG((Eq)U(Ep)<$(AG(Ep→EX((Eq)U(Ep)))→(Ep→EG((Eq)U(Ep))))(AG(p→EXr)<$AG(r→EXp))→(p→EG(Fp<$Fr))<$((AG(p→EXr)<$AG(r→EXp))→(p→EG(Fp<$Fr)p€(p)p<$Xp<$F<$p<$(p<$Xp<$F<$p)AG((p<$X<$p <$$>q<$$>r)<$(<$p<$Xp<$q<$$>r)<$))<$p<$Xp<$$>q<$r)E(Fq<$<$(AG((p<$X<$p <$$>q <$$>r)<$(<$p<$Xp<$q<$$>r)<$. AG(EXp<$EX<$p)AG(Gp<$(<$r)U(r<$p)<$(AG(EXp<$EX<$p)<$AG(Gp<$(<$r)U(r<$p)!!!!!!!!!!!“#!$“#!$#!#!#!$#!$5结论我们已经为BCTL* 提供了一个有根表。预计这将比[7]中的原始表具有更好的性能,本文中包含的基准测试表明情况确实如此。我们试图保持这个画面在其他方面与原作相似;因此,与原作相比,将其他扎根的画面与这个画面进行比较更为“公平”。通常很难直接比较此表的基准测试与[3]的基准测试,因为本文使用BCTL*,而[3]使用CTL*,但我们怀疑在某些情况下,每种技术都会优于其他技术。为了更有说服力地比较这些技术,我们将研究不同优化的效果,开发一个同样有效的CTL* 表,并使用随机生成的公式比较纯tableau技术的优点是,它们通过创建有限tableau来工作,每个步骤都基于用户提供的公式的子公式。 该输出可能对用户更容易理解。 为输出表的示例见图1。J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145159证明公式在BCTL* 中有效的优点在于,它还证明公式在CTL* 中有效。CTL*的语义可能并不适用于所有情况。尽管如此,我们认为BCTL* 的有效根表主要是朝着找到有效CTL* 表的方向迈出的一步。160J.C. McCabe-Dansted/Electronic Notes in Theoretical Computer Science 278(2011)145引用[1] Emerson,E. A.和A. P. Sistla,判定分支时间逻辑:CTL*,在:E.M. Clarke和D.Kozen,编辑,程序逻辑,计算机科学讲义164(1983),pp. 176-192.[2] Emerson,E. A.和A. P. Sistla,决定分支时间逻辑,在:第16届ACM 计算理论研讨会论文集(STOC)(1984),pp.14比24[3] Friedmann,O.,M. Latte和M.李文龙,基于表和自动机的CTL * 决策过程,载于:J.Giesl和R.Hähnle , editors , 5th International Joint Conference on Automated Reasoning ( IJCAR ) ,LNCS6173,Springer,2010. 331-345URLhttp://dx.doi.org/10.1007/978-3-642-14203-1_28[4] Mc Cabe-Dansted,J. C.,BCTL* 的有根画面(2011)。URLhttp://www.csse.uwa.edu.au/~john/papers/Rooted_BCTL_Tableau.pdf[5] Mc Cabe-Dansted,J.C.,“鲁棒性的时间逻辑”,博士。论文,西澳大利亚大学(2011年)。URLhttp://dansted.co.cc/papers/Thesis_RoCTL.pdf[6] Reynolds,M.,完全计算树逻辑的公理化,符号逻辑杂志66(2001),pp。1011-1057网址http://www.jstor.org/stable/2695091[7] Reynolds,M.,A Tableau for Bundled CTL*,JLogic Computation17(2007),pp. 117-132.URLhttp://logcom.oxfordjournals.org/cgi/content/abstract/17/1/117[8] Reynolds,M.,CTL* 的一个表,在:A。Cavalcanti和D. Dams,editors,Proceedings of the 16thInternational Symposium on Formal Methods ( FM ) , Lecture Notes in Computer Science5850(2009),pp. 403-418[9] Vardi,M.Y. 和L.Stockmeyer,程序模态逻辑的改进的上界和下界,在:第17届ACM计算理论研讨会(1985年)240-251。
下载后可阅读完整内容,剩余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直接复制
信息提交成功