没有合适的资源?快使用搜索试试~ 我知道了~
实时模型的抽象性和完备性
理论计算机科学电子笔记176(2007)5-27www.elsevier.com/locate/entcs实时模型的抽象性和完备性PetterCsabaOülveczkya,bandJos′eMeseguerba奥斯陆大学信息学系b伊利诺伊大学香槟分校摘要本文提出的标准,保证完整的实时Maude搜索和时序逻辑模型检测分析,在最大时间采样策略下,为一大类实时系统。 作为一个特殊的情况下,我们的特点是简单的条件,面向对象的实时系统的完整性,并表明,这些条件往往可以很容易地证明,即使是大型和复杂的系统,如先进的无线传感器网络算法和主动网络多播协议。我们的研究结果提供了一个大的和有用的类密集时间非芝诺实时系统的时间有界搜索和模型检测的完整性和可判定性远远超出了类的自动机为基础的实时系统,众所周知的决策程序存在。对于离散时间,我们的研究结果证明了抽象,可以大大减少状态空间,使搜索和模型检查分析可行。关键词:重写逻辑,实时系统,面向对象规范,形式分析,抽象,完备性1引言Real-Time Maude [15,12]在基于自动机的实时形式化工具(提供决策过程,如UPPAAL[7,1],Kro- nos [18]和HyTech [6])与通用建模和仿真工具之间占据了一个有用的中间地带,这些工具可以应用于更广泛的系统类别,显然超出了上述决策过程的范围,但具有非常有限的分析功能。就可指定的系统的表现力和通用性而言但就分析能力而言,它更接近于上述基于自动机的工具,尽管有一些限制。所讨论的局限性与这样一个事实有关,即由于我们处理的是一般类的无限状态实时系统,而这些系统的决策过程是未知的,因此一些形式分析是不完整的。如果发现任何反例,我们将称分析方法(例如,实时Maude1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2007.06.0056P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)5使用这样的方法是系统中的一个真正的反例;也就是说,如果该方法不产生虚假的反例。在这个精确的意义上,Real-Time Maude支持的所有正式我们称一个分析方法是完备的,如果使用该方法从未找到反例,这实际上意味着对于所讨论的分析不存在这样的例如,如果搜索从未发现任何此类违规(假设理想化的机器)实际上意味着不存在这样的违规。类似地,如果模型检查器的响应结果为真,这实际上意味着系统中不存在不符合条件的反例,那么对时间有界属性条件的LTL模型检查将是完整的。对于离散时间系统,完备性是可以买到的,但代价很高。关键在于,如果时间是离散的,那么分析可以穷尽地访问所有时刻。这使得对不变量的违反的广度优先搜索是完整的。对于决策过程范围之外的一般实时系统,无界时间导致无限状态空间,无法用标准算法进行模型检查。然而,在几乎所有感兴趣的离散时间系统都满足的非常合理的假设下,时间有界LTL属性确实具有有限的状态空间,这些状态空间确实可以进行模型检查,从而为此类属性提供完整的决策过程以这种方式实现完整性的沉重代价与这样一个事实有关,即访问所有离散时间通常会导致状态空间爆炸,使许多形式分析变得不可行。对于稠密时间系统,通过访问所有时间来实现完备性确实是相当无望的。当然,问题是,如果时间从时间r前进到时间r+rJ,其中rJ>0,则存在无限个中间时间rJ,r≤rJJ≤r+rJ,如果时钟以正的量rJ滴答,则不会被访问。Real-Time Maude通过相对于时间采样策略进行所有分析来处理这个问题。也就是说,只有那些由策略选择的时间被用来标记时间;并且只有那些状态是与所选时间相对应的状态的行为被分析。这有几个重要的优点。首先,这样的时间采样策略使其次,在关于时间采样策略和系统的非常合理的假设下,定时广度优先搜索(仅在选定的时间访问状态)可以检查所有这些状态,看看是否违反了不变量。类似地,即使有时间限制的LTL属性的状态空间现在是有限的,通过将时间限制为策略选择的时间而获得的子空间通常是有限的,并且确实可以进行模型检查。当然,由于只访问了具有选定时间的国家,这些形式分析虽然合理,但一般来说是不完整的。本文提出的问题是:在什么条件下,实时系统和时间采样策略可以保证完备性?也就是说,在什么条件下广度优先搜索成为违反不变量的完整半决策过程,P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)57对时间限制属性进行LTL模型检查(不包括next运算符即使在时间密集的情况下,这种属性也会成为一个完整的决策过程?我们在指定和分析大量实时系统方面的经验指导我们寻找保证完整性的标准。事实上,正如我们在本文中进一步解释的那样,许多实用的和非平凡的实时系统,包括我们以前分析过的许多系统,都满足我们提出的要求。如果他们使用密集的时间,这表明我们的许多分析实际上是完整的。但即使对于离散时间,这也提供了新的完整性保证,因为为了避免状态爆炸,在这种情况下,我们的大多数分析都是相对于时间采样策略进行的。关键的见解是,许多实时系统是时间鲁棒系统的一个典型示例是,每个瞬时转换由定时器的到期或具有给定传输延迟的消息的到达触发。用于这种系统的典型时间采样策略是最大时间流逝(mte)策略,其尽可能地提前时间以到达瞬时转换将被启用的下一时间。我们给出了时间鲁棒性的简单条件,也为我们所谓的我们的主要结果是,时间鲁棒系统和滴答稳定性的mte时间采样策略确实是完整的。我们证明了这个属性使用的基本概念,如抽象和口吃互模拟。关键是有两个实时重写理论(以及两个Kripke结构):原始理论和时间推进受mte策略限制的理论。限制理论的行为当然是原始理论行为的子集。我们可以把限制理论看作是对原系统的一种抽象,在性质上类似于在偏序约简方法中所考虑的那些。在偏序约简中,关键点是表明(在排除病态芝诺行为之后)受约束的、更抽象的系统与原始系统是口吃双相似的这个结果(其证明在[13]中给出)作为一个直接的推论得出,系统满足相同的LTL属性(不包括下一个运算符)。 我们也展示了这个结果如何自然地限制在时间有界的LTL属性上。这确保了我们所期望的所有完整性保证。当然,为了保证完整性,必须检查规范的时间鲁棒性 也就是说,一个完整的分析分解成两个任务:(1)在实时Maude中的标准形式分析下的mte时间采样策略;(2)检查适当的证明义务,确保时间鲁棒性和滴答稳定性。我们解决了寻找简单和易于检查的证明义务的实际问题,具体地说,我们表明,对于一个非常大的系统类,即实时面向对象的系统,可以通过消息传递异步通信的对象,如果一个遵循规范的方法8P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)5LL在[15]中主张,确实存在相当简单的证明义务,如果满足,则履行任务(2)。我们通过几个重要的例子说明了检查这种证明义务的容易性。最后,由于我们过去分析的一些系统涉及概率算法的使用,我们还讨论了如何解释这些系统的结果。本文的组织如下:第2节给出了一些背景的实时莫德和口吃模拟.第三节定义了时间鲁棒性、时间公平性、时间稳定性和时间不变性等性质,并证明了利用mtetimesam的无界和时间有界LTL模型检验对于满足上述要求的系统,实现策略是完备的。第4节展示了如何证明这些要求减少到证明基于对象的实时Maude规范的非常简单的属性,并表明这些属性可以很容易地证明我们的大型实时Maude应用程序。2实时Maude和口吃模拟的几个问题2.1重写理论隶属方程逻辑(MEL)[9]是一种类型化的方程逻辑,其中数据首先按种类分类,然后再按排序分类,每个种类k都有一个关联的排序集合Sk,因此只有种类而没有排序的数据被理解为错误或未定义的元素。给定一个MEL签名,我们记T,k和T(X)k分别表示k类和X中的变量上的k类项,其中X ={x1:k1,. ,xn:k n}是一组kinded变量原子公式有形式t=tJ(n-方程)或t:s(n-隶属关系),其中t,tJ∈Tn(X)k,s∈Sk; n-语句是这样的原子公式上普遍量化的Horn子句。 一个MEL理论就是一个对(E,E),其中E是一组E-句子.每个这样的理论都有一个初始代数T/E,它的元素是基项模可证明等式的等价类在[2]中定义的MEL理论上的重写理论的一般版本中,重写理论是一个元组R=(E,E,R,R),它包括:(i)MEL理论(E,E);(ii)一个函数f:k→kf(N)赋给一个集合f:k1··· k n → k,其中f:k 1 ··· k n→k是一个集合f(f)k {1,. ,n}的冻结参数位置;(iii)具有以下一般形式的(普遍量化的)标记条件重写规则r的集合R:(<$X)r:t−→tJ如果pi=qij∈Jwj :sjl∈Ltl −→tJ其中,对于K中的适当种类k和kl,t,tJ∈T(X)k和tl,tJ∈T(X)kl,l∈L.函数f指定函数符号f的哪些参数不能重写,这些参数被称为冻结位置。 给定一个重写理论R =(x,E,x,R),R的一个k是一对(泛量化的)同类项t,tJ,记为( xX ) t−→tJ , 其 中 X ={x1 : k1 , . , xn : kn} 是 一 类 变 量 的 集 合 , 对 k , t ,TJ∈T<$(X)k.我们说R包含<$(<$X)t−→tJ,并且i∈IP.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)59记R <$(<$X)t −→ t J,如果<$(<$X)t −→ t J可由[ 2 ]中给出的自反、传递、同余和嵌套替换的推理规则得到.2.2Kripke结构和口吃模拟一个跃迁系统是一个对A=(A,→A),其中A是一个(态的)集合,→A<$A×A是跃迁关系。给定一个固定的原子命题集合A,克里普克结构是一个三元组A=(A,→A,LA),其中A=(A,→A)是一个转移系统,→A是一个全关系,LA:A→A(A)是一个标签函数,它将每个状态与其中的原子命题集合相关联。我们将全关系写为→·,它通过为每个a添加一对(a,a)来扩展关系→,使得a→b没有b。对于重写理论R=(R,E,R,R),我们可以将Kripke结构K(R,k)L=(T/E ,k,(−1→R,k)·,L)ina tuatu a 在这些状态上的(可能是参数的)原子命题;这样的命题可以在一个保护性的扩张(ED)(E,E)中用等式定义,并以明显的方式在状态集T/E,k上产生一个标记函数LK(R,k)L_∞的转移关系是R的一步重写关系,对每个死锁状态增加一个自环。线性时间时态逻辑(LTL)公式以公知的方式为Kripke结构定义(例如,[3,5])。特别地,对于原子命题<$1和初始状态[t]上的任何LTL公式<$1,我们有满足关系K(R,k)L<$1 , [t]|[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][10][19Maude2.1[5]提供了一个显式状态LTL模型检查器正是为了这个目的。在[8]中,引入了用于关联Kripke结构的口吃模拟的概念。 对于A=(A,→A)和B=(B,→B)过渡系统,H<$A×Ba关系,如果存在严格增函数α,β:N →N,且α(0)=β(0)= 0,使得对所有i,j,k∈N,若α(i)≤j<α(i+1)且β(i)≤k<β(i+1),则π(j)Hρ(k)成立,则BH -中的路ρ匹配A中的路π口吃过渡系统H:A → B的模拟是一个二元关系H<$A×B,如果aH b,则对于A中的每条路径π,B中存在H-匹配π的路径ρ。给定一组原子命题上的Kripke结构A =(A,→A,LA)和B =(B,→B,LB),一个口吃的口吃模拟H:A → B是一个跃迁系统H:(A,→A)→(B,→B)的口吃模拟,使得如果a H b则LB(b)<$LA(a).如果H和H−1是口吃的互模拟,我们称H为口吃的互模拟;如果a H b蕴涵LB(b)=LA(a),我们称H为严格的一个严格的口吃模拟H:A → B反映了ACTL公式的满意度,没有下一个操作符如[8]中所解释的,其中ACTL是CTL对这些公式的限制其负范式不包含任何存在路径量化器[3]。特别是,ACTL将LTL作为特例。10P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)52.3实时Maude参考文献[15,14]详细描述了实时Maude及其语义。实时重写理论R是元组(T,E,T,R,φ,τ),其中(T,E,T,R)是(一般化的)重写理论,使得• φ是来自理论TIME [ 11 ]的一个方程理论态射φ:TIME→(E,E),它将时间抽象 定 义 为 一 个 有 序 交 换 幺 半 群 ( Time , 0 , + , < ) , 它 有 一 个dditionalopertosuchas−。(• (E,E)包含一个sortSystem(表示系统的状态)和一个没有子排序和超级排序且带有运算符的特殊排序GlobalSystem{_}:System→GlobalSystem,使得排序GlobalSystem的每个基项t使用方程E简化为形式{u}的项;此外,排序GlobalSystem不出现在任何函数符号的arity中;• τ是将φ(Time)类的项τ l赋值给每个重写规则l :{t}−→{tJ}如果cond涉及全局系统1排序项;如果τlφ(0)weτlJ将该规则称为tick规则,如果cond,则写r:{t}-→{t}。重写规则,非滴答规则被称为瞬时规则,并且应该花费零时间。系统的状态应该具有{u}的形式,在这种情况下,滴答规则的形式确保时间在系统的所有部分均匀地前进的排序GlobalSystem的重写α:{t}-→ {t J}的总时间流逝τ(α)是在一个特定规则中的时间流逝之和[11]。如果在R中有证明α:{t}−→{tJ },其中Τ(Α)= R,则我们可以证明R <${ t} −r→{t J}。我们写时间,0,。. . ,用于φ(时间)、φ(0)等。Real-Time Maude扩展了Full Maude [5],以支持将实时重写理论指定为定时模块和面向对象的定时模块。尽管实时Maude在时域中是参数化的,其可以是离散的或密集的,它提供了一个滴答规则应该(特别是对于密集时间)具有以下形式之一:crl [l]:{t}=>{tJ} in timex if cond/\x< =u/\condJ[nonexec]. ( †),crl [l]:{t}=>{tJ} in timex if cond [nonexec].(b)或rl [l]:{t}=>{tJ},时间x [nonexec]。(§),其中x是一个排序为Time的变量,它不会在{t}中出现,也不会在条件中项u表示时间在一个刻度步长中可以前进的最大量条件cond和condJ(可能为空)不应进一步约束x(除非可能添加条件x= 0)。这些形式的规则通常是不可执行的,因为在重写步骤中不清楚给x分配什么值;我们的工具通过选择不同的 例如,最大时间采样策略将时间提前最大可能时间在形式为(†)的规则中流逝u(除非u等于INF),并尝试提前时间通过具有其它形式的滴答规则中的用户给定的时间值r。时间非确定性报价规则的所有应用--无论是重写、搜索还是模型检查--1 所有涉及排序术语GlobalSystem的规则都假定具有不同的标签。P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)511的t0使用所选择的时间采样策略来执行。这意味着系统中的一些行为,即通过不同地应用报价规则获得的行为,不被分析。实时重写理论RmaxDef(r),nz表示实时重写理论其中根据最大时间采样策略应用滴答规则并且其中不应用将时间提前0的刻度步长。“非定时”重写理论R C是通过向状态添加“时钟”分量从R获得的,使得全局状态是ClockedSystem排序的时间r中的形式{ t }的当选择最大时间采样策略时,Real-Time Maude首先在内部将实时重写理论R和命令转换为理论(RmaxDef (r) ,nz)C(或其扩展,取决于要执行的命令),然后在Maude中执行相应的命令。本文主要研究了实时Maude的无界性搜索和LTL模型检查命令。在无界模型检验中,我们在最大时间采样策略下,检验了LTL公式。每个路径 在 (RmaxDef(r),nz)C启动与 的状态 的t0 及时0. 为 时间-有界模型检验与时间界Δ,我们只考虑路径的路径(RmaxDef(r),nz)≤ΔRC-在时间限制Δ时表示在[15]中解释,其中我们还定义了无界和时间有界的满意度(R,L,t0|= Φ和R,L,t0|= ≤Δ Φ)。3时间鲁棒系统在本节中,我们定义了时间鲁棒的实时重写理论,并证明了使用最大时间采样策略的无界和时间有界搜索和模型检查分析对于时间鲁棒理论的定时公平路径是合理和完整的,假设原子命题满足关于滴答步骤的某些时间鲁棒系统是指:(i) 从任何给定的状态开始,时间可以提前(i)任何数量,(ii)任何数量直到并包括特定的时刻,或者(iii)根本不(ii) 推进时间并不影响上述性质,除非时间一直推进到上述情况1-(ii)中的特定时间界限。(iii) 即时重写规则只能在特定时间应用,即当系统将时间提前了最大可能量时。这种时间鲁棒系统的一个典型示例是,每个瞬时转换由定时器的到期或具有给定传输延迟的消息的到达触发。我们的经验表明,许多大型系统确实是时间鲁棒的。一个时间鲁棒系统可能有芝诺路径,其中无限个滴答步骤的持续时间之和是有界的。我们在芝诺12P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)51Max∞RJ由规范强加在系统上的路径(这可能表明系统设计中的错误)和由于tick增量中的错误“选择”而导致的Zeno路径直观地说,第二种类型的芝诺行为不反映系统中的现实行为,因此不能用最大时间采样策略来模拟。因此,我们称之为定时公平路径,这些路径的系统,不表现出第二种,不切实际的芝诺行为。在第3.4节中,我们指出,在时间鲁棒实时重写理论3R和理论RmaxDef(r),nz中的定时公平路径集合之间存在一个口吃互模拟,如[8]2中所定义的,该理论定义了滴答规则的系统。根据最大时间采样策略应用。这个定理的完整证明以及其他证明在[13]中给出。 这一主要结果是通过证明对于每个定时公平路径π在(Kripke结构相关联与)R,在(与关联的Kripke结构)中存在对应的路径ρRmaxDef(r),nz与[8]中解释的π这样一种不连贯的互模拟意味着每一条无限路径都可以被适当地模拟,unbounded属性第3.5节给出了一些条件,这些条件足以证明时间公平路径的每个时间有界前缀都可以由使用最大时间采样策略获得的时间有界路径来模拟,从而我们也得到了时间有界公式分析的完备性。3.1时间鲁棒的实时重写理论最大策略可以处理两种不同类型的报价规则应用:• 从时间只能前进到某个最大时间的状态开始的滴答• 时间可以任意提前的状态。最大时间采样策略通过尽可能提前时间来处理第一种滴答步骤,并通过将时间提前用户给定的时间值r来处理第二种滴答步骤。定义3.1一步重写t-r→tJ,使用报价规则,持续时间为r是:• 最大节拍步长,写作t-r→tJ,如果没有时间值rJ>r,Jt−1→ tJJ 对于一些TJJ;• 一个∞tick步长,写为t-r→tJ,如果对于每个时间值rJ>0,有一个tickRJrewritestept−1→tJJ;以及rJJ J• anon-maxima lticktepifthereisamaximaltickstept−m→ax 不对于r>r.例3.2下面的规范模拟了一个密集时间的逆行时钟,其中{clock(24)}项应该总是显式地重置为{clock(0)}。2 尽管我们处理路径集来处理定时公平路径略有不同。[3]此外,所考虑的命题集必须满足关于滴答步骤的一些性质P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)5131111∞1R就在该复位操作之前或之后,时钟可以检查其是否剩余足够的电池容量,或者其是否必须通过进入一个状态而立即停止{clock-dead(...)} .(tmodSIMPLIFIED-Dense-CLOCK正在保护POSRAT-TIME-DOMAIN。opsclock stopped-clock:Time->System[ctor].varR R ':时间。crl[tickWhenRunning]:{clock(R)}=>{clock(R+if R <' = 24 monus R [nonexec].rl[tickWhenStopped]:{stopped-clock(R)} =>{stopped-clock(R)}在时间R ' [nonexec]。rl[reset]:clock(24)=> clock(0)。rl[batteryDies1]:clock(0)=>stopped-clock(0). rl[batteryDies2]:clock(24)=> stopped-clock(24)。endtm)从状态{clock(5)},存在无限个非最大滴答步长,例如, 到{clock(10 +2/7)},以及到{clock(24)}的最大刻度步长。从{stopped-clock(24)}从术语到其本身有∞个刻度步长,时间了理论R具有时间鲁棒性的第一个要求是,每一个tick步长要么是最大的,要么是非最大的,要么是∞的tick步长。这排除了具有密集时域的规范,其中时间可以从某个状态前进任何严格小于某个值Δ的量,但时间不能从同一状态前进时间Δ或更多具有形式为†、和其中条件cond和condJ不进一步约束x将满足该要求。下一组假设涉及覆盖所有行为而不执行非最大滴答的能力。我们必须确保一系列非最大滴答后面跟着一个最大滴答可以通过一个最大滴答步骤来模拟,并且执行非最大滴答不会导致行为(死锁,其他滴答可能性,采用瞬时规则等)。不同于那些可以被最大的蜱虫覆盖。因此,我们增加以下要求:r+rJ如果t−m→ax不是一个最大的节拍步长,并且t−r→tJ是一个非最大的节拍,那么应该有一个最大的节拍步长tJRJ−m→ax不JJJ 对于一些TJJJ .同样,如果t−r→tJ是a非最大刻度步长和tJJ−m→ax tJJ 是一个最大的滴答步,那么一定有一个r+rJmaxim alt ickstept−m→ax 不JJ. 最后,为了确保没有瞬时规则被忽略,如果t-r→tJ是r>0的非最大滴答步长,则存在isnoinstaneuson-steprewritetJ−in→sttJJ。接下来我们考虑∞tick steps。为了使系统具有时间鲁棒性,执行∞tick步骤不应导致应用瞬时规则的可能性,也不应排除采取进一步∞步骤的可能性。因此,如果t-r→tJ是一个∞tick步长,r>0,那么从tJ开始也有一个∞tick步长,并且cannbenoinstantaneoussteptJ−in→sttJJ。 这些标准本身只能确保一旦我们执行了∞tick步骤,所有剩余的步骤都将是∞tick steps,我们可以有一个∞tick steps的序列,其中时间在每一步中提前r。对于我们想要的互模拟结果,关键思想是每个无限序列的∞tick steps由另一个这样的序列模拟。然而,在这些状态和持续时间之间不需要有任何关系。JJ14P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)5111∞1R两个序列的∞步骤。为了进行正确的口吃模拟,我们还必须考虑这些命题。Real-Time Maude假设零时刻度步骤不会更改系统状态;因此该工具不会应用刻度规则将时间提前0。因此,我们要求,如果t−0→tJ是一个tick步长,对于基项t和tJ,时间提前0个时间单位,那么t和tJ在系统的基本方程理论中必须是等价的。我们将时间鲁棒性的要求总结如下:定义3.3实时重写理论R是时间鲁棒的,如果以下要求TR1至TR6 对于排序GlobalSystem的所有基础项t、tJ、tJJ和排序Time的基础项r、rJ、rJJ成立:TR1。使用刻度规则的每个单步重写是最大、非最大或∞刻度步骤。r+rJTR2。t−m→ax不和非最大节拍步长t−r→tJ这意味着存在最大tick step tJRRJ−m→ax不JJJJ 对于一些TJJJ。JRJJTR3。对于t−1→tr+rJ步骤t-m→ax 不非最大刻度步长,tJJ.−m→ax不这意味着存在一个最大的TR4。如果t−r→tJ是r>0的一个阶跃,且dtJ−in→sttJJ是瞬时的一步重写,则t−→ tJ是一个最大的节拍。TR5。 t−r→ t J这意味着有tJJ,rJ使得tJRJ−∞→t JJ.TR6。 t = t J在基本的方程理论中对于任何0时间刻度步长t −0→ t J都成立。3.2芝诺行为与时间公平对于密集时间,典型的滴答规则的形式使得在系统中具有“Zeno”被分配器成为可能,为了分析的目的,区分由“错误选择”引起的关于增加多少时间的Zeno行为和规范强制系统的Zeno行为(这表明模型中的设计错误)似乎很重要在后一类中,我们还包括瞬时规则的无限序列应用的情况例如,重写序列一个半四分之一八分之一t0−→ t1−→ t2−→ t3−→···是一种芝诺行为,由系统中错误的时间推进选择引起,rl [tick]:{t}=>{g(t,x)},时间为x。然而,芝诺重写序列一个半四分之一八分之一{f(1)}−→{f(2)}−→{f(4)}−→{f(8)}−→···JJP.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)51511是crl [tick]:如果x = 1/N,则在时间x中{f(N)}=>{f(2 * N)}<。由于时间不公平,我们将忽略所有具有无限序列的滴答步骤的路径,在每个步骤中,时间可以前进到时间r0或更长,但路径的总持续时间永远不会达到时间r0。另一个计时不公平问题涉及这样一个事实,即系统可以在滴答规则中连续将时间提前0如果这是时间可以从一个状态提前的最大量,那么这样的坏序列不被上述非芝诺要求所覆盖。在我们的时钟示例中,系统可以连续地应用tick规则到状态{clock(24)},以在最大可能时间0内达到相同的状态。考虑到0时间滴答不应该改变系统的状态,我们要求“公平”路径不包含仅由以下组成的0-只要可以应用瞬时规则,时间就会滴答作响。我们将timedFairPaths(R)定义为满足上述两个要求的理论R的路径集合,并将LTL公式关于此类时间公平路径的无界满足定义如下:定义3.4给定一个实时重写理论R,一个GlobalSystem类的项t0和一个time类的基项r,集合Paths(R)t0是所有无限序列的集合。π=(t0在时间r0−→t1在时间r1− →··−→ti在时间ri−→··)的RC-状态,其中r0=0,使得• 对于每个i,ti-→ti+1是具有持续时间r(当应用瞬时规则时为0)的一步重写,其中r i +r=ri+1;或者• 存在k使得在R中不存在从t k的一步重写,并且使得对于每个j > k,t k= t j和rk= r j,并且对于所有ik,有一个单步滴答重写tj−r→tJ,其中 Δ≤rj +r,那么一定有一个l,Δ≤rl;• 对于每个k,如果对于每个j> k,持续时间为0的最大节拍步长和如果我们的规则可以在j中应用,则这一规则必须是这样的,即,tl+1是一个单步重写应用瞬时规则为一些l> k。我们将[15]中的满意度关系扩展到定时公平路径,如下所示:定义3.5给定一个实时重写理论R,一个定义原子状态和钟控命题的RC的保护扩展L,一个排序GlobalSystem的项t0,和一个LTL公式Φ,我们定义满足,没有时间限制,16P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)5Π关于定时公平路径如下:R,L,t0|= tfΦφ ππ,L C|= Φ 对于所有路径π ∈ timedFairPaths(R)t0。3.3时态逻辑命题与节拍为了模型检验的目的,原子命题应该满足一定的“稳定性”的要求,相对于滴答步骤,使最大时间采样策略,以模拟所有定时公平路径。对于无界模型检查,我们可以允许一组时态逻辑属性的赋值在一系列滴答应用中改变一次。如第3.5节所述,对于时间约束模型检查,属性不应因不是最大刻度步长的刻度步长而改变。下面的例子表明,对于无界分析,没有必要要求命题不被刻度步长改变:实施例3.6(实施例3.2)在我们的时钟例子中,我们可以定义一个命题ge20,如果时钟显示的值大于或等于20. 这个命题在ticks下不是不变不过,这样的提议--在无界分析的最大时间采样策略下, 因为它只改变一次 在从{clock(0)}到{clock(24)}。 因此,术语{clock(0)}可以从{clock(0)}到时钟值小于20的滴答序列中的最后一个状态的步骤,并且项{clock(24)}可以模拟剩余的步骤。然而,如果我们添加另一个命题ge 22,这两个命题的估值可能在一个滴答序列中改变两次,并且{clock(0)}和{clock(24)}都不能表示,例如,#21040;的状态。最大时间采样策略永远不会找到一个包含满足ge 20/1 ~ ge 22的状态的行为。同样地,命题clockIs 20(仅对状态{clock(20)}成立)既不能被{clock(0)}也不能被{clock(24)}“模拟”。对于无界模型检验,我们需要假设所考虑的命题集是tick稳定的,在这个意义上,如果t−r→1t−r→2·· ·r−n−→2tr−n→−1t11211n−1maxn是一个非最大刻度步的序列,后面跟着一个最大刻度步,那么有一个i k,tlPtnP.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)517∞∞LLΠLLΠLLLRLR• t−r→tRJJJJJJ而tJJ−∞→tJJJ隐含tJJJJPTJJJJ当r>0。此外,t−r→ tJ和t−∞→t暗示TPt对于r,r>0。对于闭合程序4,对于每个rj,时间tt=t-r→tJ应该被等效地时钟化重写,时间t=RJ-→tj=RJ通过时间值RJ,则命题p必须在时间RJ中对于时钟状态t成立,当且仅当它在时间RJ+r中对于时钟状态TJ成立。3.4无界模型检验在本节中,我们证明了R,L,t0|= tfΦ成立当且仅当RmaxDef(r),nz,L≠,t0|= Φ保持,对于R是时间鲁棒的实时重写理论,Φ是LTL公式,并且L是扩展RC的标记函数,使得出现在Φ中的原子命题满足滴答稳定性要求。这个等价性通过证明P是一个严格的口吃互模拟,Kripke结构K(RC,[ClockedSystem])C,限于其定时公平路径,Π和K((RmaxDef(r),nz)C,[ClockedSystem])C。 此外,互模拟是Π在《易经》中,《易经》的解释是:引理3.8设R是一个时间鲁棒的实时重写理论,r是R中大于0的时间值,L是R C的一个保护扩张,它定义了命题P,P是一组滴答稳定的原子命题(其中一些可以被计时,一些可以被解锁)。然后,P:K(RC,[ClockedSystem])LC→ K((RmaxDef(r),nz)C,[ClockedSystem])CΠ当K(RC,[ClockedSystem])CΠ 被限制到定时公平路径。上述引理的逆也成立(证明在[13]中给出):引理3.9关系P是严格口吃P-模拟P:K((RmaxDef(r),nz)C,[ClockedSystem])LC→K(RC,[ClockedSystem])CΠ当K(RC,[ClockedSystem])CΠ 被限制为定时公平路径。定理3.10设R是一个时间鲁棒的实时重写理论,r是R中大于0的时间值,L是RC的一个保护扩张,它定义了一些命题,P是一组tick稳定的原子命题(其中一些可以被计时,一些可以被解锁)。 则P是K(RC,[ClockedSystem])C之间的严格口吃P -互模拟,限制于其定时公平Πpaths和K((RmaxDef(r),nz)C,[ClockedSystem])C。Π[4]一个状态是否满足一个时钟命题不仅取决于状态,还取决于它到达状态所花费的总时间。18P.C. 奥尔韦茨基Meseguer/Electronic Notes in Theoretical Computer Science 176(2007)5≤Δ的t0证据 直接从引理3.8和3.9得出,因为P等于(P)-1,P是对称的。Q下面的主要结果,其证明也在[13]中给出,表明最大时间抽样分析是可靠和完整的:推论3.11设R,t0,r,L_∞,P如定理3.10所示,设Φ为LTL_∞公式,其原子命题包含在P中,则R,L,t0|= tfΦ当且仅当RmaxDef(r),nz,L,t0|= Φ。3.5基于最大时间抽样策略的有时限模型检验的可靠性和完备性Real-Time Maude不仅时间有界属性本身是相互关联的,而且当使用Real-TimeMaude的时间采样策略时,模型检查分析会终止非Zeno规范中的时间有界属性此外,即使当可达状态空间是有限的,使用最大时间采样策略可以大大减少状态空间,使时间有界模型检查可行。我们在[15]中定义了时间有界属性的语义。从本质上讲,一个有时间限制的公式是在所有可能的路径上解释的,在在此语义中,时间有界属性<<“在一个步骤中从时间0的时钟状态{clock(0)}到时间24的状态{clock(24)}的节拍步骤。然而,根据我们的语义,该属性确实与时间界限24保持我们用timedFairPaths(R)≤Δ表示Paths(R)≤Δ的子集(参见[15]),t0t0包含在状态t0开始的所有定时公平路径,如[15]中所解释的,这些路径在时间Δ处被截断 满足关系|时间公平路径上的=tf的推广以一种明显的方式达到有时间限制的满足:定义3.12R,L,t0|= TFΦ 成立当且仅当 π,L|= Φ对所有π∈ timed
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功