没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记155(2006)401-421www.elsevier.com/locate/entcs多模型检验的自动机博弈Altaf Hussain and Michael Huth阿尔塔夫·侯赛因和迈克尔·胡特1,2英国伦敦帝国理工学院南肯辛顿校区计算机系,邮编:SW7 2AZ摘要3-值模型被提倡作为系统抽象的一种手段,使得时间逻辑属性的验证和反驳从抽象模型转移到它们所代表的系统。然而,某些应用程序域需要一个具体或虚拟系统的多个模型。我们建立了3值属性验证和反驳的数学基础,适用于有限多个模型的常见具体化集。我们证明了模态μ演算的有效性检查在这些集合上与所有2值模型具有相同的成本(EXPTIME-完全),提供了一个有效的算法来检查是否存在固定数量的模型的共同具体化,并建议使用树自动机变体上的奇偶游戏来有效地近似多个模型的有效性检查。证明了文[25]中的泛拓扑模型不是有界完备的。这证实了上述近似仅对于树型自动机模型是合理精确的,除非所有模型都被假设为确定性的。关键词:模型检测,一致性,奇偶博弈,聚焦转移系统,树自动机。1引言模型检查[37,7]创建并决定判断M|其中M是计算系统的模型,φ是属性,并且|=指定哪些模型享有哪些属性的满意度关系。在这种情况下,抽象被广泛认为是对抗臭名昭著的状态爆炸问题的关键技术,即模型的大小通常是系统可观量或过程数量的指数。近年来,人们越来越多地使用1电子邮件:ah701@doc.imperial.ac.uk2电子邮件:M. doc.imperial.ac.uk1571-0661 © 2006 ElsevierB. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.11.067402A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)4013-模型检查和程序分析中的有值系统抽象(例如[10,11,38,4,16,17])。这种抽象模型是三值的,因为静态和动态信息以两种模式指定:这种方法的主要好处是,|= φ holds)和反驳(M| = φ不成立)可以很好地转移到它们所建模的具体系统中,而这只适用于2值情况下的普适路径性质的验证[ 8 ]。在谓词抽象工具(如SLAM [2]和BLAST [20])中对具体系统的抽象传统上是一种“安全模拟”,并且只允许验证这种通用路径属性。抽象的三值方法并不局限于此,在形式化方法中,越来越需要结合存在和通用路径量化器的属性,以利用所观察到的测试、模型检查和仿真环境的然而,在许多情况下,对单一模型的推理是不可取的、不可接受的或不可能的。我们陈述一些例子。• 在需求工程中,利益相关者为一个系统制定期望或方案,每个这样的观点都可以被解释为一个模型。• 联邦数据库提供了单个数据存储库的假象,但每个本地数据库可以被解释为单个数据模型• 在软件验证中,计算机程序可以通过不同的工具或抽象域进行抽象,每个工具或抽象域都产生该程序的模型。• 今天• 在UML建模中,很少有单个消息序列图,所有相关图表的集合是分析的自然主题所有这些例子都表明,人们想要对有限多个模型M1,...,M k共同地,并且各个模型M i受益于3值,因为对于M i来说,外部的状态和事件可以被合并为可能的信息,而M i中已知的状态和事件被表示为必须的信息。 例如,如果数据库Mi没有命题p,可以安全地假设p在Mi中可能为真,但不知道为真。 如果C(M)是一个3值模型M的2值具体化的集合,例如通过精化[31]或抽象解释[9,10]定义的,那么对M的模型检查需要对整个集合C(M)进行合理的推理,因为任何K∈ C(M)都可能是M建模的实际系统。集体推理A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401403因此,有限多的模型会推理出以下形式的集合:Ki=1C(Mi),(1)本文的主要研究对象在二值模型检验中,|= φ一个关于M的具体化集C(M)的原因,M是Stone空间中用于互模拟的等价类的单例[22]。在3值模型检验中,具体化的集合C(M)在那个Stone空间中是一个紧集合[22]。因此,从2-值到3-值模型检验的过渡可以在拓扑上解释为从单值紧集到更一般的紧集的过渡,这些紧集是从单值3-值模型M和精化生成的,其中C(M)是精化M的那些2-值模型的集合。因此,(1)中的集合在所述商空间中作为紧集合的有限交也是紧的。因此,我们的论文可以被看作是将3值模型检验扩展到(1)中的紧集,通过在这种设置下发展3值模型检验[4,5]中的两个熟悉的研究问题。• 问题1。理解模态μ演算在(1)中集合上的满足性和有效性检查• 问题#2. 寻求近似这些决策问题的有效方法。在从单个紧集C(M)到这些集的有限交集的过程中,我们还面临着一个新的决策问题,即一致性问题。(1)中的集合可以是空的,因此不存在所有Mi的公共具体化。因此,我们确定了第三个研究问题,在这种情况下。• 问题#3. [1]在[1]中,对于固定的k,有效地判定集合的非空性。我们论文我们的论文完全解决了问题#1和#3,审查和评估了问题#2的现有提案,并提出了问题#2的新解决方案。我们还表明,问题#2的任何合理的解决方案不能依赖于模型检查单合成3值模型,除非这些模型具有类似于树自动机的结构,或者对所有模型Mi进行特殊的确定性假设。文件概要我们使用基于状态的Larsen第三节阐述了本文研究的三个决策问题,并证明了404A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401·其中两人的边界很窄在第4节中,我们提出了一个有效的算法,用于确定固定k时形式为(1)的集合的非空性。第5节讨论了Dams Namjoshi第6节陈述了一些相关的工作,第7节结束。2基本概念和背景在整个过程中,我们固定了一元模态Q和命题的有限集合AP定义2.1(i)克里普克模型K是一个元组(R,R,L),其状态集为,转移关系为R×,标签函数为L:→P(AP)。(ii) 模态Kripke模型M是一个元组(tuple,Ra,Rc,La,Lc),其中(tuple,Ra,La)和(tuple,Rc,Lc)是Kripke模型,Ra<$Rc,La(s)<$Lc(s)对于所有s∈tuple。在适当的时候,我们将模态Kripke模型称为(iii) 在方便的时候,我们将Kripke模型(R,R,L)视为模态Kripke模型(R,R,R,L,L),反之亦然。(iv) 我们称(M,s)为初始状态为s的点模态Kripke模型M。模态Kripke模型背后的直觉是Ra和Rc\Ra分别指定模型的必须和可能转换[31];而La和Lc标签分别断言已知为真和可能为真的信息[24]。Rc和Lc的补语指定不可能性,例如。(s,SJ)/∈Rc表示从状态s到SJ的转变的不可能性。我们使用模态μ演算[28](μL)作为属性语义。许多分支时间时序逻辑,例如CTL [3],可以用μL表示,φ::= q| Z | ¬φ| φ∧φ| Q φ |μ Z.φ(2)其中q∈AP,Z在递归变量的可数集Var上。我们把<$Q <$φ写成Qφ。在最小不动点公式μZ.φ中,μZ将φ中Z的所有出现与静态作用域绑定在一起,我们要求φ中Z的所有自由出现都在偶数的否定作用域下。一个公式φ是封闭的,如果它不包含自由递归变量。语义学[|·|] m模态Kripke模型映射上的μL公式φ和环境ρ,函数Z<$→(ρa(Z),ρc(Z))的Var→型{(L,U)|L},转化为图1中分析模式m∈ {a,c}的状态集。A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401405ρρρ[Z<$→A]ρ[|Q|] m= L m(q)[|Z|] m=ρm(Z)[|¬φ|] m=\[|φ|]<$m[|φ1∧ φ2|] m=[|φ1|] m[|φ2|] mρ ρ ρ ρ ρ[|Q φ|] m= pre m([|φ|] m)[|μZ.φ|] m= lfp λA。[|φ|] m.ρ ρρρ[Z<$→A]Fig. 1.模式m∈ {a,c}的模态Kripke模型上μL的语义,其中<$a=c,<$c=a,且prem(A)={s ∈ N|当m ∈ { a,c }时,(s,sJ)∈ Rm}. lfp表示最小不动点运算符,这里应用于函数λA。[|φ|]m:P(N) →完备格的P(π)(P(n),n).定义2.2我们写s| = aφ for s∈ [|φ|] A;相似地|= cφ表示s ∈cρ[|φ|] ρ。 如果φ是封闭的,我们就省略了多余的环境ρ。注意,对于m∈ {a,c},我们有s| = mQ φ i for all(s,sJ)∈R<$m,sJ| =mφ。所以Q是一个通用的量化器,它被评估为|= m在 m 的双模式<$m中的后继状态上。注2.3若K是Kripke模型(K,R,R,L,L),则[|φ|] a=[|φ|] c持有ρ ρ在K中,对于μL的所有ρ和φ[24],因此这定义了标准的Kripke语义K|= ρφ为k ∈ [|φ|] a对于K的所有状态k。例2.4在图4的模态Kripke模型中,我们有s1|= aQ p,因为所有从s 1出来的R c跃迁都导致状态sJ(这里只有t1),其中p∈L a(sJ),并且s1|=cμZ。(<$p<$$>q)<$Q Z,因为存在一条R c-路径s1R c t1R c u1,到达状态u1,其中u1|= c<$p<$q.在指定模态Kripke模型时,我们通过一个精化概念隐式地描述了Kripke模型C(M)的可能无限集合。这个概念,定义如下,基本上是Larsen Schlossen在[31]中的概念定义2.5(i)对于i=1,2,设(Mi,si)=((Mi,Ra,Rc,La,Lc),si)为我我我点模态Kripke模型则(M1,s1)被(M2,s2)i定义为存在一个关系Q1 ×2,使得(s1,s2)∈Q,对于所有的(s,t)∈Q,我们有(a) 对所有q∈AP,s∈La(q)蕴涵t∈La(q),1 2(b) 对所有q∈AP,t∈Lc(q)蕴涵s∈Lc(q),2 1(c) 若(s,SJ)∈Ra,则存在(t,TJ)∈Ra且(SJ,TJ)∈Q,1 2(d) 若(t,TJ)∈Rc,则存在(s,SJ)∈Rc且(SJ,TJ)∈Q.2 1(ii) 我们写(M1,s)<$(M2,t),只要存在这样一个Q,其中(s,t)∈Q,在这种情况下,我们说(M2,t)精化(被抽象为)(M1,s)。(iii) 我们将C(M,s)写为(M,s)的具体化集合,定义为C(M,s)={(N,t)|(M,s)<$(N,t),(N,t)是Kripke模406A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401型}。A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401407Qpt1u1pTJ 111KS1图二.一个Kripke模型K使得(K,s1)∈ C(M1,s1)对于图4中的模态Kripke模型M1。证 明 这一点的一个精化关系由Q ={(s1,s1),(t1,t1),(t1,tJ),(u1,u1)}给出。上面的条件(c)规定了细化必须保持必须的过渡;而条件(d)表示细化必须反映可能的过渡;标签的行为与(a-b)中所述的类似例2.6图2显示了图4中模态Kripke模型(M1,s1)的具体化(K,s1),关系式Q={(s1,s1),(t1,t1),(t1,tJ),(u1,u1)}作为一个见证的精炼。由于加固件是传递的,(M1,s)<$(M2,t)蕴涵C(M2,t)<$C(M1,s)。在[23]中,也证明了相反的含义。因此,如果可以捕获(1)单个模块的集合的集合中的集合,KC(M)=i=1C(Mi),(3)n个M i是所有Mi的任意一个重新定义,并且是所有的MirefinesM。这是一个很好的,在部分订单报价的refinemPre或rderM是所有M i的最小值。在第5节中,我们将展示这一点在一般的非确定性的情况下,上确界细化与我们的属性语义很好地吻合,并以属性语义为特征。定理2.7([24])(i)对于所有的点模态Kripke模型(M,s)和(N,t),我们有(M,s)<$(N,t)i <$(对于μL的所有闭的、不动点的方程φ,s∈ [|φ|] aimplies t∈ [|φ|] a)。(ii) 如果(M,s)<$(N,t),则s∈[|φ|]aimpliest∈[|φ|[a],且t∈[|ψ|]c暗示s∈ [|ψ|] c,对于μL的所有闭φ,φ。这个定理保证了[|φ|我是相对于彻底的语义而言的。408A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401[5]中的Bruns Godefroid的抽搐。这种可靠性在以下推论中被捕获为组合的欠近似和过近似,这是[5]中结果的重新表述。推论2.8([5])对于任意闭φ∈μL和任意模型M的任意状态s:(i) 下近似:如果s ∈[|φ|]a,则φ对所有(K,k)∈ C(M,s)成立.(ii) 过逼近:如果φ对某个(K,k)∈ C(M,s)成立,则s ∈ [|φ|]c.3多模型及其决策问题我们现在可以定义本文所研究的决策问题。随后,让V ={(M i,s i)|1 ≤i≤ k}(4)表示点模态Kripke模型(Mi,si)的任何有限集合,每个模型都有一个有限的状态集我们确定了相关的决策问题。定义3.1LetC(V)=C(M,s)(5)(M,s)∈V是V的共同具体化的集合。我们定义参数化布尔表达式C(V),S(V,φ)和V(V,φ),其中φ是μL的任何闭合公式:(i) 一致性:C(V)保持i = V的所有模型具有共同的具体化,即i =C(V)/={}。(ii) 可满足性:S(V,φ)为真,如果V存在共同的具体化满足φ,即i <${(N,t)∈ C(V)|不|= φ} /={}。(iii) 有效性:V(V,φ)保持i ≥ V的所有公共具体化满足φ。由于所有的点模态Kripke模型((R,Ra,Rc,La,Lc),s)都有一个具体化,例如((R,Ra,La),s),C(V)成立,因此V的所有模型都有一个共同的精化。注意,V(V,φ)对所有φ成立,如果V没有公共加细。所以,在想证明V(V,φ)之前,应该先建立C(V)证明上述所有三个决策问题都可以简化为Kripke模型上μL的满足性检验是一件常规的事情。受[29]的启发,我们为每个点模态和有限状态模态Kripke模型(Mi,si)构造了μL的封闭公式[Mi,si],使得对于所有点模态Kripke模型(N,t),我们有(N,t)|= a [M i,s i]i <$A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401409(M i,s i)<$(N,t).(六)410A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401我我在[22]的定理4.8(2)中已经证明了模态转换系统的这类公式的存在性和C(V)的约化。下面的定理仅仅是这个结果的一个小小的推广定理3.2(i)对于所有的点模态Kripke模型(N,t),每个点模态Kripke模型(Mi,si)都有一个μL的公式[Mi,si]满足(6)。(ii)决策问题C(V)、S(V,φ)和V(V,φ)都是EXPTIME在φ的大小中,可简化为满足性检查k[Mi,si],K Ki=1i=1[Mi,si],有效性检查φ模型(分别)。证据i=1[Mi,si],μL,Kripke(i) 对于Mi中的每个状态ti,我们设置,类似于[29]中的(3):[i,i]=((ti,tJ)∈RaQ[Mi,tJ])<$Q((ti,tJ)∈Rc[Mi,tJ])(7)我{q|q∈L a(t i)}<$我{<$q|q/∈L c(t i),q∈ AP}作为最大不动点方程组。由于Mi只有有限个状态,每个[Mi,ti]都可以用μL表示。[Mi,si]对于所有点模态Kripke模型(N,t)满足(6)的证明基本上是[31]中给出的证明。(ii) 我们可以通过证明V在封闭公式中有一个共同的具体化,将C(V)简化为μL的σV=Ki=1[Mi,si](8)的μL是令人满意的Kripke模型。• 如果σV满足,则k| = σV对于某个点Kripke模型(K,k)。由于(K,k)可以转换为点模态Kripke模型,(6)和k| = σVrender(M i,s i)<$(K,k)对于所有i = 1,2,.,k,所以(K,k)∈C(V).• 相反,如果V有一个共同的具体化,比如说(K,k),我们有(Mi,s i)<$(K,k),对于所有i = 1,2,.,k.使用(6),这意味着(K,k)|= σV,所以σV在Kripke模型上是满意的。S(V,φ)和V(V,φ)对满足性检查的减少,单位为μL,C(V)的减少的变化。检验S(V,φ)保持i<$φ <$σV在Kripke模型上是满意的。检查V(V,φ)保持i <$$>φ <$σV在Kripke模型上是不可满足的但μL的合格性检查在EXPTIME [14].QA. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401411i=1我我我我图1的语义,一个在推论2.8中指定的近似,是通过类似于[5]中的2值检查的简化而在UP中实现的。对于S(V,φ)和V(V,φ)来说,这样的约简一般是不可能的,因为这些决策问题是EXPTIME-完全的。定理3.3判定问题S(V,φ)和V(V,φ)在φ的大小上是EXPTIME-完全的.证据对于V={(M,s)},S(V,φ)和V(V,φ)问(M,s)的某些(分别是所有)具体化是否满足φ。因此S(V,φ)是文[5]中BrunsGodefroid的广义模型检验问题,V(V,φ)是它的对偶问题.由于广义模型检验问题对于模态μ演算[5]的公式是EXPTIME-完全的,所以S(V,φ)和V(V,φ)对于μL的一般V和φ是EXPTIME-困难的,其大小为φ。 根据定 理3.2 , 判定问 题S( V , φ) 和 V( V , φ) 在 φ大小 的EXPTIME中,因此是EXPTIME完全的。Q4有效一致性检验实际考虑建议研究定理3.2(ii)的上界是否可以对C(V)降低,我们现在对(1)中的固定k定义4.1(i)我们表示乘积状态空间kΣi byΣV,写t for(t1,t2,.,t k)∈ ∈ V,并使用Vs强调si是( 4 ) 中 V 的 每个(Mi,si)中的初始状态。(ii) V的一个常见的精化证明是关系W∈V,使得t∈W蕴涵(a) 对所有i和q∈AP,如果ti∈La(q),则对所有ji=i,tj∈Lc(q),(b) 对于所有i,如果(ti,TJ)∈Ra,则存在某个tS∈W,其第i个nate等于tJ,使得对所有j i,(tj,tJ)∈Rc.I j注意,在上面的子句(b)中,tS的第i个坐标绑定到给定的tJ。由于共同细化见证人的任意并集是一个共同细化见证人,所以对于每个V s,存在一个最大的共同细化见证人,记为dbyWVs。 这种关系说明存在共同定义。定理m4.2对于Vs,原函数C(Vs)等价于“s∈WVs”.证据• 我们通过证明W={t∈SVs|C(Vt){}}这是对WVs的一种补充。给定t∈W,根据W的定义,有(K,k)=((SK,RK,LK),k)∈ C(Vt).·条款(b):对于任何i,如果(ti,tJ)∈R a,则存在(k,kJ)∈RK,其中(M i,tJ)<$(K,kJ)为(M i,t i)<$(K,k)。由于(Mj,tj)<$(K,k)对于所有ji=i412A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401我return{};let(bad(t,No))=//定义4.1(ii)的子句(a)失败:((somei,j,q| t_i inL^a(q)&¬ t_j in L^c(q))||//定义4.1(ii)的子句(b)失败:(R^a中的某些(t_i,x)|Sigma_V中的所有t'减去否|x = t'_i ==>一些j|R^c中的not(t_j,t_j ')))在{ while(Sigma_V中的某个t减去No|(bad(t,No){ No = No union {t};}Yes = Sigma_V减去No;//删除所有失败图三.计算WVs对于给定的一组视图Vs,其中union和minus分别表示集合论的并和补。该算法计算一个最大不动点,并最初且(k,KJ)∈RK,存在(tj,tj)∈Rc,其中(Mj,TJ)<$(K,KJ)对每个J Jj/=i. 特别是,VtS 具有(K,kJ)的一个自适应收敛性和tS∈W。·类似的推理适用于clause(a)和soWW WWVs。• 现在我们证明所需的等价性。(i) 若C(Vs)成立,则通过定义ns∈W,W∈WVs,通过项above.(ii) 设s∈WVs。我们定义了K=(WVs,R,L)的约束条件,Vs如下:(t,tS)∈Ri 对所有i,(t,TJ)∈Rc(9)我 我t∈L(q)i 对所有i,ti∈Lc(q)对于q∈AP。我们称(K,s)∈ C(Vs),有加细{(ti,t)|t∈WVs}表示g(Mi,ti)∈(K,t),其中i=1,2, . . , k和allt∈WVs. 通过定义,从K中的t∈WVs或在K中的t处的任意y变换对于每个Mi中的ti是“c -匹配的”。 相反,任何a-跃迁(ti,tJ)Mi,其中t∈WV确保对于所有ji,SsSjSt∈WVs等于t∈WVs So(t,t)∈R,当Ra∈Rc在Mi中. Sincet∈WVs这是共感应工作的。 类似的论证适用于ti∈La(q)和ti∈La(n)。因此(M i,s i)<$(K,s)对于所有i = 1,.,k,所以C(Vs)成立。Q图3示出了计算WVs的一个租赁。 如果Vconsistsofwopointed Kripke模型,则算法非最优地计算它们的最大互模拟。我们注意到,细化证人的概念同样适用于定理4.2对于这样的集合仍然有效。图3中的算法的符号版本也可以处理这种适当统一的无限集合例4.3图4显示了两个模态Kripke模型;{(s1,s2),(t1,t2)}是一个常见的精化证明,也是最大的一个,因为所有其他元素都是A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401413Qq?pt1u1S2 q?t2pM1M2S1见图4。两个模态Kripke模型,其中虚线(实线)表示Rc\Ra(分别为Ramust-标签,La(s)的元素,写在状态s内,may-标签是Lc(s)\La(s)的元素,用“?"注释。例如,q∈Lc(s2)\La(s2), p∈ La(t1).101×102没有共同的修饰。例如,对于(u1,s2)∈R1×R2,有(s2,t2)∈Ra,并且没有从u1到与t2具有公共精化的状态的输出Rc跃迁。定 理 4.4 图 3 的 算 法 最 多 在 |1995 年 |iter-a-tionsandassignmentstooYesthesetWVs.证据对于终止,Sigma V减去No初始等于Sigma V,No是Sigma V的子集,在每次迭代时增加1,因此迭代次数不能超过Sigma V中的元素。它仍然显示正确性:• 对于WVs对于许多非空的共同定义的WSVs, WSigmaVminusNo是while语句的不变量。包含物W=Sigma V减去No最初保持不变,因为No为空,W为Sigma V。假设WSigmaV minusNo正好在while 语句的 迭代之前 给定t∈W, 表达式 ( bad( t,No))是假的,因为t在公共精化见证W中,并且quantier all t'的范围是集合S V m i nu s N o and d substances W by a ssumpt i o n。 因此,可以将not∈Wcn添加到No.• 对于YesWavesit successsto showt h ttanon-emptyYesisacommonfinne-mentwitness. 在赋值给非空的Yes之后,表达式(bad(t,No))对于Yes中的所有t都为false,因此这表明Yes是一个公共的为V的最后一个证人。Q414A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)4015自动机游戏我们希望得到EXPTIME完全判断S(V,φ)和V(V,φ)的有效逼近。由于μL的2值模型检验可归结为确定谁在奇偶博弈中具有获胜策略[27,33],因此我们寻求S(V,φ)和V(V,φ)的近似,允许类似的约简。现有的解决办法及其不足之处。人们可以基于模型合并的思想来寻求这样的近似[40,21]。通过在模型上施加类似于[30]中使用的确定性条件,合并模型的过程能够产生最小的com,monrefinementM对于一致的模型,使得(3)成立[40]。唉,确定性要求严重限制了模型的表达能力。模型合并的思想也可以应用,如果没有确定性的解释正在进行。在[21]中,根据由(V−,s)<$(Mi,si)<$(V+,s)(10)对于所有i = 1,2,.,k.所以(V−,s)是一个公共抽象,而(V+,s)是所有(Mi,si)的公共精化,如果C(Vs)成立。不幸的是,(V-,s)和(V+,s)的具体化的集合通常是(1)中非空集的差近似,并且这种差的主要原因是单模型近似,我们现在详细说明这一点。定理5.1存在有限状态模态Kripke模型(M1,s1)和(M2,s2),使得对于任意点模态Kripke模型(M1,s2),C(M1,s1)<$C(M2,s2)不具有C(M1,s2)的形式。证据我们采用矛盾证明,[17]的结果,以及[25]的模型理论见解。在[17]中,我们证明了3值模型及其精化的各种概念因此,本文将模态转移系统作为三值模型来证明这一定理考虑(假设)任何两个点有限态模态转移系统(M1,s1)和(M2,s2)都有一个点模态转移系统(M1<$M2,s1<$s2),使得(11)成立:C(M1<$M2,s1<$s2)= C(M1,s1)<$C(M2,s2)。(十一)A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401415如果是否定的,那就是否定的。在[25]中,构造了一个SFP-域(D,≤),使得所有的有限状态模态转移系统(M,s)都有一个嵌入的|M,s|对于所有有限状态模态转移系统(N,t),(M,s)refines(N,t)i|N,t |⟩ ≤ ⟨|M,s|(12)(M,s)(D,)|M,s|),(13)(D)|M,s|(M,s).(十四)特别地,(D,≤)是一个偏序,其中所有有向集都有一个超确界.从[23]中,我们得知,对于所有的点模态转移系统(N,t)和(M,s),我们有( N , t ) ( M , s ) iC ( M , s ) C ( N , t ) ,( 15)如果部分是非平凡的。根据(12)和(15),我们推断:|M1<$M2,s1<$s2|的上确界⟨|m1,s1|和|m2,s2|当(11)成立时,则(D,≤)成立。通过假设定理是假的,一个点模型(M1<$M2,s1<$s2)满足(11)对于所有的有限状态模型都存在,其中(11)的右边是非空的。特别地,在D中有界的D的任何两个紧致元素k和l(即存在某个d∈D,其中k≤d且l≤d)在D中具有上确界,因为所有紧致元素都是[25]中某些有限状态点模态转移系统的嵌入。由于D是代数的,这意味着在D中有界的任何两个元素的上确界存在,因此D是有界完备域。但D的任何非空子集都有一个下确界[1]。 我们将推导出这是一个矛盾的存在这样的fima如下。假设(N1,t1)和(N2,t2)是点有限状态模态Kripke模型,如图5所示。根据[17]中的结果,我们可以假设这些模型并且下面讨论的所有模型都是模态转换系统,因此我们可以考虑将它们嵌入到D中。出于同样的原因,只要方便,我们可以把任何模态转换系统看作模态克里普克模型。“我,我。|n1,t1|⟩ ∧ ⟨|N2,t2|存在维生素D并且可以被解释为一个点模态转换系统(D,i),具体如下在[25]中。特别地,(N1,t1)和(N2,t2)的任何两个公共抽象(A1,a1)和(A2,a2)使得有嵌入是Jea ch(Ni,ti)的边界:|Aj,aj|⟩≤⟨|NjJ,tjJ|对于一个llj,j∈{1,2}。因此,通过(12),我们得出结论:⟨|A j,a j|n ≤(D,i)(j= 1,2)当i = n时|n1,t1|⟩ ∧ ⟨|N2,t2|<$(16)(A j,a j)<$(D,i)(j= 1,2).(十七)416A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401现在考虑点有限状态模态Kripke模型(A1,a1)和(A2,a2)A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401417Rq?t1p?Sq?t2p?R的1p?Sasr?sq?一个2p?一个2DDD的1DN1N2A我N1N2u1u2w1w2图五. 两个点模态Kripke模型(N1,t1)和(N2,t2),其中AP ={p,q,r,s},不具有最大公共抽象,如定理5.1的证明所示。A1A2ar x2阿派2见图6。两个尖模态Kripke模型。两者都是图5中描述的指向模态Kripke模型(N1,t1)和(N2,t2)的常见抽象。 然而,(A1,a1)和(A2,a2)的共同加细并不是(N1,t1)和(N2,t2)的共同抽象,如定理5.1的证明所示。图6中的很容易看出,两者都是(N1,t1)和(N 1,t 1)的抽象。(N2,t2),因此(16)和(17)对于(Aj,aj)选择是这样的由于(a2,x2)∈Ra且(A2,a2)<$(D,i),存在某个(i,IJ)∈Ra等那x2iJ.但是一个1i以及Ra阿夫拉克所以A1的某个态ω其中(a1,ω)∈Rc ,ω∈IJ. 最后,i<$t1和i<$t2与(i,IJ)∈Ra暗示存在某个(t1,η)∈Ra且(t2,γ)∈Ra使得iJn且iJ∈γ。 特别是ωη、ωγ、x2η和x2γ(18)因为精化是传递的,并且iJ充当(18)中所有四个精化实例因此,如果我们可以证明不存在这样的状态η和γ。因为每个ti都有两个Ra- 继任者我们需要考虑四种情况:(i) 设(η,γ)=(u1,u2). 由于ω通过(18)抽象了状态u1和u2,我们418A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401的1的1的1的1从u1处的标号推断出ω∈Lc(r). 从u2,我们同样得到ω∈Lc(s). 但Lc(r) Lc(s) 是空的,是矛盾的。(ii) 设(η,γ)=(u1,w2). 由于ω通过(18)抽象了状态u1和w2A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401419的1的1的1的1的1的1的1的1一个2一个2我们从u1处的标号推出ω∈Lc(r)。从W2,我们同样得到ω∈Lc(p)。但Lc(r)黎巴嫩c(p)是空的,是矛盾的。(iii) 设(η,γ)=(w1,u2). 由于ω通过(18)抽象了状态w1和u2我们从w1处的标号推出ω∈Lc(p)。 从u2我们同样得到ω∈Lc(s)。但Lc(p)黎巴嫩c(s)是空的,是矛盾的。(iv) 设(η,γ)=(w1,w2). 由于x2通过(18)抽象了w1,因此我们从在w1上x2∈Lc的(p)。 但x2/∈Lc(p) 一个定义,一个定义,措辞总而言之,不是所有的(N1,t1)和(N2,t2)都有关于前序的下确界。“假”是假的,“假”是真的。Q推论5.2 [ 25 ]的域D不是有界完备的。证据 这个证明隐含在定理5.1的证明中,因为有界完备域对于在该域中有界的所有子集都有上确界。Q让我们对定理5.1及其证明作几点说明(i) 无法在单模态Kripke模型上获得S(V,φ)和V(V,φ)的良好约简以进行模型检查,这与[25]的域理论模型D不是有界完备的事实有关。因此,这种方法只能提供有限的结果,并在本节的剩余部分中激励对树自动机模型及其改进游戏的考虑。(ii) D不是有界完备的这一事实似乎与Dams& Namjoshi在[12]中讨论的验证模态μ演算模型检查M的不完备性有关|= φ通过模型检查A| = aφ在有限状态抽象A上。因为如果X是元素d的集合,使得(D,d)|=aφ,[ 12 ]意义下的完备性要求非空X在D中有一个极小元素(它是X的一个下确界,也是X的一个元素)。(iii) 定理5.1的证明依赖于这样一个暂时的假设,即D中的无穷点对所有的元素对都存在。这些对不需要是一致的或违反确定性条件,将安全(3)。实际上,图5中选择的示例模型(N1,t1)和(N2,t2)是不一致的,因为它们没有共同的具体化。这不是问题在于,我们将420A. 侯赛因,M。Huth/Electronic Notes in Theoretical Computer Science 155(2006)401我们提出的解决方案。在使用树自动机模型提出我们的建议时,我们只关注有效性检查,为了清晰起见,过度简化了随后的技术讨论。 总的来说,我们在很大程度上依赖于Dams Namjoshi在[12]中的工作。我们针对问题2提出的解决方案的关键思想是• 模态Kripke模型M和μL的公式φ同样具有作为一种树自动机的有效表示,[12]的聚焦转移系统(FM,相应地Fφ)• 聚焦转换系统F识别树L(F)的语言• 因此,σV∈μL可以表示为这样一个聚焦跃迁系统,FV,以及• 聚焦变迁系统的EXPTIME-难语言包含问题L(FV)<$L(Fφ)可以用UP_∞_co-UP来近似,其中有[12]中的某个奇偶博弈Fφ±FVK设σ为[M,s],如(8)中所示。 该μL公式具有有效的编码Vi=1i i作为一个对应的树自动机AV,它完全接受那些Kripke模型满足σV。类似地,我们有一个针对φ的树自动机Aφ。然后,这些树自动机被有效地表示为聚焦转移系统[12]AV和Aφ,分别如上文所述。前引书(Thus,FV定义为AV,Fφ定义为Aφ。)第七章Loc引用, A φ|= A φ用于模型检查游戏在锁。引用, 哪里|=对应于我们的|= a,因此欠近似有效性检查。根据定理6,引用,我们得到一个V|= A φ,前提是AV定义A φ(在[ 12 ]中写作AV±A φ),用于图3中的抽象博弈移动。前引书因此,可以用loc的(奇偶)博弈检验AV±Aφ来欠近似V(
下载后可阅读完整内容,剩余1页未读,立即下载
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)