没有合适的资源?快使用搜索试试~ 我知道了~
160《理论计算机科学电子札记》65卷第6期(2002)网址:http://www.elsevier.nl/locate/entcs/volume65.html20页基于时间自动机菲利普·卢卡斯1Lehrstuhlfur?rInformatikIIRWTHAachen,Germany摘要消息序列图(MSC)提供了一种快速和易于理解的并发系统建模方法。除了从它们的视觉语法中容易地推导出它们的直观语义之外,还有一种形式上定义的语义--不幸的是,直观地赋予它们的语义有时与形式上的语义不一致。在本文中,我们将展示一种替代方法的MSC的语义,这将使我们能够正式建模其定时行为。此外,我们展示了如何排序事件的一些概括可以导致更适合于模型现实世界的要求的语言。为了简化分析(高级)MSC的任务,我们确定了可以转换为有限(定时或非定时)自动机的子类,并指定了转换,从而为模型检查奠定了基础。1介绍消息序列图(Message Sequence Chart,简称MSC)是有限数量的进程之间有限数量的消息交换的图形或文本表示。MSC的语法在ITU标准中定义[21]。[21][13]的附录中定义了官方语义。MSC可以被组织在高级消息序列图(HMSC)中。HMSC是将MSC与每个节点相关联的有限图,指定系统可以通过沿其路径连接MSC来展示的行为序列(参见[27] MSC的介绍)。虽然语法允许定量的时间行为的具体化,但对象语义仅捕获定性行为,即。e. 我们可以指定,消息只能在自最后一个动作起经过4个时间单元之后发送,但是过程代数语义仅使用消息只能在最后一个动作之后发送的事实。1电邮地址: phlucas@i2.informatik.rwth-aachen.de,02159/528601·c2002PublishedbyElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。卢卡斯161∈很明显,在实时系统的开发中,需要一种分析定量时间行为的规范的方法。已经有各种方法来扩展语义或定义替代语义来弥补这个缺点。在[5]中,作者给出了一个有效的过程,用于确定对事件之间的时间具有某些限制的MSC是否(“该消息的转换时间为x [1]。六四0个字符]时间单位”是可以实现的。[18]这是一种更进一步的方法。MSC也是如此。 此外,委员会认为,勒厄 和BEN-ABDALLAHpoint在可能的直观解释之间存在一些重要的语义差异时间限制,我们稍后会详细讨论。在[16]中,作者研究了如何通过将指定转换为观察者自动机,来检查作为时间自动机集合的系统是否可以在本文中,我们将首先定义MSC和HMSC的语法和语义。这将是通常基于执行序列使用的定义的保守扩展:我们允许MSC包含由[21]指定的共域和一般排序,并将级联运算符推广为能够处理同步,异步和其他类型的级联。我们相信,这种对事件顺序的定义和MSC的串联比迄今为止已知的许多论文中使用的更容易适应各种现实世界的场景,可以减轻分析MSC的理论家和试图在没有正式背景的情况下理解这种正式规范的实践者的生活。基于这种离散语义,我们将使用定时约束和定时器为HMSC提供定时语义,作为[21]所指定的那些的为此,我们将集中于HMSC,因为MSC可以被视为HMSC的特殊情况在第5.1节中,我们会记得,并不是所有的HMSC都可以转换为有限自动机,因为自动机应该准确地识别那些形成HMSC的无时间语义的事件我们将确定一个子类的收敛HMSC。它将表明,收敛的HMSC可以被翻译成有限自动机,并且由这些自动机定义的语言等价于用于定义HMSC的语义的语言。HMSC是否收敛是可有效判定的。例如,在[6,19,10,22]中给出了没有定时约束的MSC的语义的自动机理论表征。我们需要调整这些想法,以应对在我们的正式定义中引入的一般化。第5.2节给出了时间HMSC到时间自动机的转换。这也是一个保守的扩展的无定时的情况。 有大量关于TA分析的文献:[2,28,9,20,4,1,11,12]可以作为良好的起点。 我们相信,充分理解的TA将有助于在未来-真正分析更容易理解的前端规范语言,如MSC,通过提供一个强大的后端,直观的规范,卢卡斯162可以翻译。结果的更详细解释和动机可以在[24]中找到。2消息序列图MSC是一种非常自然的建模进程间通信的方法。2从语法上讲,我们通过为每个进程绘制垂直线并在这些线之间为每个消息交换绘制箭头来描绘MSC。因此,在图1中,两个进程参与通信,其中进程1向进程2发送两消息可以被标记。这是为了描述信息的传递。我们将在正式语法中支持标签,但不会在我们的示例中使用它们为了便于讨论,我们将在一个图形化定义的MSC中枚举消息,并且我们将引用消息的发送事件i通过si发送到相应的接收事件,通过ri发送到相应的接收事件。时间应该在每条生产线上向下移动(因此,在我们的例子中,s1发生在s2之前)。如果过程线上的一些事件没有排序,我们说它们位于一个协域中,并通过对过程线的相应部分划虚线来可视化。为了指定事件的顺序,否则这些事件将是无序的,我们在它们之间画一条虚线。这被称为一般排序。MSC通过它的处理顺序和只能接收发送的消息的要求来定义部分顺序。在图1中,r1和r2是无序的,但r2有发生在S2之后。流程的本地操作使用方框来描述。这意味着图1中发送的消息可以以任何顺序接收,并且在进程2接收消息1之后的某个时间,它执行本地操作。行动将被标记。图1使用一般排序的12一21大多数分析不允许局部动作(不允许过程之间同步的事件)、共域和一般排序。是因为-[2]虽然MSC直到上个世纪末才被标准化,但同样的符号已经使用了很长时间(参见[23]早期的例子)。3也有一个正式定义的文本语法,但MSC的优点在于,容易学习的视觉规范具有形式上定义的语义。因此,我们在示例中使用图形语法卢卡斯163≺≺联系我们{∈}≺E S R A I O Ctomary假设一个过程中事件的线性顺序另一个由[21]定义的概念是计时器。计时器是一种能够从初始化时间倒计时到0的设备。它与单个进程相关联,不能被任何其他进程使用。进程可以初始化计时器,停止计时器并注意到它们的超时。目前,我们把这些事件看作是简单的行动。我们使用事件的偏序对MSC进行建模。这里,偏序应该是传递和不相关的二元关系。它可以被理解为某种依赖关系:如果e只能在eJ发生时发生之前,然后是eJ e。MSC的语义将被定义为所有序列不 违 反 偏 序 所 施 加 的 限 制 的 事 件 。一全 序 是 偏 序 , 其 中 a , b.a<$b<$b<$a<$a=b。全序是偏序的线性化。l(n)表示所有这些线性化的集合。 因此,l(k)将为我们提供MSC的语义,该命令对它的事件。因此,在一般讨论的例子中,=(s1,r1),(s2,r2),(r1,A),(s1,s2)+s1<$r1<$A<$s2<$r2和s1<$s2<$r2<$r1<$A将是n的线性化。为了便于记谱,我们把线性化写成词,e。G. s1r1As2r2∈ l(n).除了使用计时器,我们还为每对分配e事件的eJ依赖关系P:=xQ:x0类似于[α,β]来表示e和eJ可以由不小于α且不大于β的时间单位分开(P应该是P上的所有区间的集合)。这是必要的,因为否则就不容易表达过程线上的两个事件e和eJ之间的距离不能超过µ单位:我们可以设置一个计时器到μ,但是我们不能轻易地确定这个事件会发生在e附近,所以计时器很可能被设置为,比如说,在e之后2μ单位。此外,我们可以将每个局部动作与持续时间相关联。我们的意思是,当动作发生时,执行动作的过程不能做某事“做点什么”的含义仍有待正式确定。我们将在语义的讨论中涵盖两种方法。现在,我们将确定MSC的形式化我们使用的方法在许多文件中使用的保守G. [26])时间限制和更一般的命令。定义2.1(定时)MSC是一种结构.Σ哪里M:=P、E、o、m、N、N、l、T、τ、N、x,• P是进程名的有限集合(简称进程•是一组有限的事件,分别分为发送和接收事件、(本地)操作、定时器初始化、超时和定时器停止卢卡斯164P≺≺≺我→CUPEI O C≺• o:E → P将每个事件与它所属的过程相关联;对于p∈ P我们定义Ep:={e∈E:o(e)=p},对于S,R,A,I,O,C也是如此;• m:S → R对相应的发送和接收事件进行双射匹配;• E ×E是E上的一个偏序,称为M的序,满足m;我们设对任意p∈ P,• Λ是标号字母表;• l:S <$A →Λ是一个标号函数;• T是一组有限的计时器;• τA:A→T将每个动作与其持续时间联系起来,τ=ττA;• P:P将定时器的每次初始化与它被设置的时间相关联;• χ:I = 0·C → T将每个定时器相关事件与其定时器相关联。除非另有说明,所定义的符号总是在这个意义上使用。对于MSCMν,事件的集合是ν,对于所有的符号,依此类推;我们还写(M)来表示MSCM的排序,依此类推。M(,Λ)是具有进程集和标记字母表Λ的所有MSC的集合。MSC有时被称为基本MSC。请注意,我们没有施加进一步的限制,除了它是一个部分订单。特别地,我们不假设每个过程上的事件的总排序,因此允许在[21]中定义的共域,但是我们也不要求消息遵守所谓的因果排序([25]),其中一个过程线上的事件的顺序不能由过程强制执行,而没有对底层介质或其他细节的特定需求取决于现实世界(从不同过程接收消息的事件r1,r2,其中不存在引起传递依赖性r1s2)总是被认为是无序的。MSC正在建模的介质上的已知限制(如FIFO队列或[15]意义上的有界性)可以在这里被处理,或者,如果这不可能,稍后 自动机的定义我们定义了MSC的两种语义:非定时语义仅使用以确定解释为动作的线性化,而定时语义也使用τ给出的限制。这将在后面使用,我们将首先定义非定时情况下的自动机,然后将它们用作构造定时自动机的基础。此外,它允许分析MSC仅关于其离散语法。MSC的定时语义将在定时HMSC的上下文中给出有些作者不直接使用事件来定义语义,而是只考虑事件类型。原因是我们可能无法区分从进程p到进程q的两条消息,因此发送事件e,eJ都被视为某种事件类型的实例,比如p!Q. 来照顾卢卡斯165EE →∈≺ ⊆ E∀∈∀≺∈在这里,我们使用映射π:π来定义一些字母表的语义。对于所描述的解释,我们将使用=和π= id或像许多论文中定义的消息类型字母表(例如,G. [10])。我们将使用这样的信息字母表来简化符号。Sp,q(λ),Rp,q(λ)分别表示从进程p到进程q的标记为λ∈Λ的消息的发送和接收事件,Ap(λ)是对p的动作λΛ,IT(μ),CT,OT分别表示定时器T的初始化(到μ)、清除和超时这种从事件到它们的类型的映射将用σ表示,这些类型的集合是(基于m,o,,χ和λ的σ的形式定义是显而易见的)。在上面讨论的简单例子(图1)中,给出的线性化将是S1,2R1,2A2(A)S1,2R1,2和S1,2S1,2R1,2R1,2A2(A)。请注意,如果消息携带相同的信息(相同的λ),我们就失去了感知消息超越的能力。 在[10]中,这个符号被扩展以应付超车。定义2.2设M是MSC。M在π下的非定时语义是<$M; π)0:={π(l):l∈l(n)}. 我们简单地写<$M)0而不是<$M; id)0。为了定义我们的自动机,我们将使用一种在文献中以许多名字命名的装置。我们的术语如下[18]。在自动机中,我们希望跟踪到目前为止发生的事件。 显然不是 允许事件的所有子集发生,但仅允许与兼容的子集发生。切割边缘(简称切割)是一组事件K哪里eK. eJe.eJK. 这意味着一个cut代表了一个可能已经发生的事件的有效历史记录,而不管它们的顺序。K(M)是MSCM的所有切割的集合。切割K=E称为完全切割。在图2中,我们可视化切割{s1,r1,A,B,s2}。4图2MSC的切割边缘1一2BB一CC一个MSC不足以模拟许多真实的例子。人们可能想模拟这样一个事实,即系统首先表现得像MSCM1,然后表现得像MSCM2。因此,这些MSC的级联必须被定义。[21]定义异步级联(任何p∈ P必须完成任何[4]由于共区域的存在,并非所有的切割都能以这种方式可视化卢卡斯16612pp啪啪啪啪∅∈ ◦\◦p∈P12p∈P12222e∈ Ep之前,它可以进行到一个eJ∈ Ep)。 同步级联,其中MSC必须在系统进入前完全工作,接下来的MSC,也是相当受欢迎的。我们相信,为了现实世界的系统建模,我们必须考虑的级联操作的泛化。假设在图3的设置中,系统从M1开始,然后移动到M2。在任何情况下,要求线性化来遵守r1和r2都是没有用的,但是我们必须有可能强制执行这一点。因此,我们得到了共区的扩展和分离MSC和MSC的一般排序是指对系统模型中可能出现的非常不同的级联语义进行建模。图3待连接的M1M212131232形式上,设M1,M2∈M(P,Λ).设ρ∈E1×E2。然后,在ρ,M1与M2的级联,M1<$ρM2,被定义为MSCM,事件E:=E1E2和:=(<$J<$$>J<$ρ)+,其中M的所有其他成分都如人们所期望的那样定义。表示不相交的并集,即,e.对于某些集合u,v,u v:=({1}×u)<$({2}×v).通常我们用e来表示(1,e)(和(2,e))。如果我们有理由不这样做,我们写(1,e)e并将e扩展到包含e的最小等价关系。我们让他联想到左边。我们用ρ=E1×E2得到同步协调,通过使用ρ=E × E,以及一个连接参数对应于文献中广泛使用的因果排序,MSC通过ρ =E ×(AS I C)。 在本文中,后者将是称为弱异步级联。ρ=表示平行组成,的意义[21]。重新访问图3,s2r2s1r1<$M1<$M2)0<$M1{(r1,r2)}M2)0:对事件顺序的附加限制限制了语义。3高级消息序列图在第一小节中,我们将我们的考虑限制在HMSC的非定时行为上。这最好地捕捉了基本属性。然后,我们定义HMSC的语义也关于它们的定时行为。卢卡斯167◦E/2004/10∼3.1非定时HMSCs高级MSC(High-Level MSC,简称HMSC)5是一个有限有向图,它有一个不同的起始节点和一组结束节点。在我们的设置中,节点用MSC标记。我们将把HMSC描述成标准的自动机。的语义通过HMSC的运行被给出为相应MSC的级联的语义。HMSC的语义是从开始节点到结束节点的所有运行为了沿着路径连接MSC,我们使用关系k产生连接ρ的参数ρ。 这背后的直觉是,有无限数量的MSC由包含循环的HMSC定义,但对某些此类MSC的事件的依赖关系完全由图上使用的边定义。当我们正式定义语义时,这将变得更加清晰。在下面的例子中,对于任何集合u,有r(u):={t:t<$u}。定义3.1HMSC是一种结构H:=。N,(M)n哪里ii=1,N,E,k,τ,• N ={1,...,n}对于某个n∈N是节点数(节点)的集合;•M1,...,M,n分 别 是每 个 节 点 的MSC,其中i=在任何情况下,并且所有事件集合都是成对不相交的;• N是一组端点;• EN×N是边关系,其中对于任何节点i,都有从1到某个iJ∈Nnn通过i;• k:E+→ r(E × E)(其中我们令E=ni=1 Ei等)是MSC间优先关系k(i1,i2)<$Ei1×Ei2;• τ:(i1,i2)∈E+k(i1,i2)→P是MSC内关系τ到MSC之间的事件通过HMSC的路径是从某个i到任何j的任何路径,其中路径将由访问节点的序列表示。通常,序列w的元素由w i表示,其中1 ≤i≤|W|.所有这些运行的集合是运行(H,i,j)。 游程H是从1到某个j∈N的所有游程的集合。现在,让我…l s是通过HMSC的运行,让M是由它定义的MSC。当我们通过访问另一个节点ls+1来扩展运行时,我们必须找到得到M<$ρMl的正确ρs+1. 由于k,我们对任何MSC M lv,1 ≤ v ≤s,依赖关系k(lv,ls+1)。ρ则包含所有这些关系,修改后的适合照顾。 由于技术原因,有必要提供语义也用于运行的片段。5 有时候,术语消息序列图(Message Sequence Graph,MSG)也被用来描述这些结构。卢卡斯168HMSC1:HMSC2:M1M1M11r2S∗一B12一B1M1定义3.2设H为HMSC,对于MSC,设π:E →(a) 对于某些lJ∈游程(H)且1 ≤g1g2<<. 0)片段nt1=l1. . lr:=lgJ1.. . lgJr定义(不定时)MSCm(l):=Mlα(l1,l2)Miα(l1l2,l3).. . α(l1. lr−1,lr)Ml,其中α(l1. l s,l s+1)定义如下:E∈ E(Ml1◦α(l1,l2)Ml... α(l1. ls−1,ls)M l). f∈ E(M ls+1)它认为:Iv∈{1,.,s}。ej∈E(Mlv). (e<$ej<$(EJ,f)∈k(lv,ls+1)),则(e,f)∈ α(l1. l s,l s+1)。(b) 这样的l在π下的(无时)语义是<$l;π)0:=<$m(l);π)0。的(untimed)semantics of H under πis<$H;π)0:=像往常一样,如果π= id,我们就省略πl∈runs(H)<$l; π)0. 6图4语义的规律性现在我们来看看图4中的HMSC。应该都清楚知道如果我们使用异步级联,HMSC 1的语义可以通过正则表达式(s1r1s2r2)来定义。另一方面,HMSC 2使用异步要有规律因此,并非所有的HMSC都可以转换为有限自动机,我们需要一些属性来识别合适的HMSC。我们的“收敛”概念由于我们对串联的定义更为一般,所以它与它们中的任何一个都不完全一致假设H是HMSC,并且l:= 11. l n l1是一个简单的厕所。p通过它(i. e.l1∈/{l2, . ,ln})。 发送群S(l)由yS(l):=E(l1. . ln)0),→其中→:=(11. l n)0)ni,j=1k(l i,l j)。 对于任何节点x,y,我们定义d(x,y)是k在从x到y的路径上创建的边的最小数目,6π必须以规范的方式推广到π-等价事件2卢卡斯169day.7H称为收敛的,如果对任何简单循环l,S(l)是强连通的(d(x,y)是对任何循环事件x,y定义的);否则我们称H为发散的。例如,在图5的HMSC中,我们考虑循环并且看到使用弱异步级联的HMSC是收敛的。 我们观察到从r2到s1的路径必须使用至少两个k-边,如r2→ A和r3→s1,所以d(r2,s1)= 2。图5小型HMSCM1M1C1一23B一稍后,我们将为收敛的HMSC定义自动机定理5.2表明,对于任何循环的所有元素,d(x,y)的存在对于HMSC是可平移的是足够的,但是我们可以直观地理解d是关于什么的。假设对于某个MSC的每对事件,d(x,y)= 1这意味着,对于MSC中参与简单循环的任何事件e,该MSC的先前实例化必须在它的另一个事件发生之前完全工作d(x,y)=n> 1意味着我们可以潜在地经历这样的循环多次,直到在先前实例化的切割中缺少事件而阻碍进展。收敛意味着对于任何x,y,d(x,y)被定义。因此,如果没有观察到某些事件,循环最终必须停止。e.如果我们非常频繁地通过一个MSC,我们就有足够信息来推断出在一次运行中该MSC的前面出现必须是完整的。3.2定时HMSCs图6语义不明显的定时HMSCM1H:T,10M2不7形式上,定义k-边的权重为1,所有其他边的权重为0,让d(x,y)是最短路径的权重M1M2da11卢卡斯170da不∈∈不不不不考虑图6中的HMSC。在M1中,定时器T被设置为10个时间单位。T在M2中经历其超时。如果进程1在其结束之前停止T超时时,我们将使用符号×代替,并省略箭头。如果一次运行从11开始,因此访问了T的设置两次,会发生什么?基本上有两种不同的方法:我们可以(1)将其解释为设置两个不同的计时器,(a)让它们都超时,按照它们设置的顺序,或者(b)假设它们都必须同时超时。或者(2)我们假设只有一个定时器T。在这种情况下,它让我们决定(a)我们是否在第二次运行通过M1时将T重置为10个单位,或者(b)忽略它,只关心第一次设置,或者(c) 将其视为错误并丢弃这样的运行。任何一种解释在某些情况下是合理的,不应该受到完全的谴责在[8]中观察到,这样一个具体化的语义并不十分明显。应该能够以这样一种方式定义语义,以允许不同的建模要求,特别是保持形式语义与直观分配的含义的强烈相似性。为了定义语义,我们需要时间词的概念,即。e.每个字符都用时间戳修改的单词。 这是值得思考的事件发生的时间正式地说,一个计时词超过了αbet∈saw或dw∈(T×T)n,其中T:={x∈R:x0},在其中hichee第二分量的序列形成单调递增序列。为了演示自动机的构造,它只给出了情况(2a)的语义。这将被表示为()>。为了简化符号,让next(w,i,X,Y)是在w i+1. W|W|,使得在wi+1. W|W|;否则,next(w,i,X,Y)是unfined。定义3.3设H为定时HMSC。run、π等被定义为不定时的HMSC。设l∈游程H,M=m(l). l的>-语义在π,<$l;π)>is<$l;π)>:={π(w):w∈<$M)0<$w∈(E×T)<$,则对于任何i∈ {1,.,|},满足以下条件}|}, the following conditions are fulfilled}• (w服从τ)∈ E。(j=next(w,i,{e},{wi})<$tj−ti∈τ(wi,e)),以及(wi∈A<$wj∈E(o(wi))<$j> i)<$t j−ti τ(wi))。• (任何定时器最终被检查,并且没有定时器被检查,其不运行)对于yT∈ Tit成立:Ifσ(wi)=IT,定义下一个(w,i,{CT,OT,IT},IT);如果σ(w i)∈ {CT,OT},则i =下一个(w,j,{CT,OT},{IT}),对于<满足σ(w j)= IT的ji。• (w服从于σ)如果σ(wi)=IT,则:如果j=next(σ(w),i,{OT},{CT,IT}),则t j−t i=<$(w i);如果j = next(σ(w),i,{CT,IT},{OT}),则t j−t i<<$(w i)。<$H;π)>:=l∈runs(H)<$l; π)>. 像往常一样,如果π= id,我们就省略π注意,对动作的要求意味着我们在线性化中分配给动作的时间是该动作的开始时间。 此外,委员会认为,我们可以争辩说,一个过程不应该只做一些事情,卢卡斯171E\ORE|不操作,因此允许进程在执行操作时通知超时或接收消息。 在上面的定义中,我们取o(wi)(o(wi)o(wi))代替fo(wi),并且后面定义的自动机可以很容易地相应地改变。对于计时器,我们要求我们注意到超时,也就是说,我们不能默默地重置已经超时的计时器4时间自动机时间自动机(Timed Automata,简称TA)是由ALUR和DILL([3])提出的。在[1]中可以找到一个很好的概述。 与离散词的自动机相比,TA接受定时词,这使得它们特别适合我们的任务。我们将只使用在当前设置中有用的TA部分。设A是通常意义上的确定性有限自动机,i。e.离散词的自动机我们用有限数量的时钟来修正自动机,这些时钟在自动机处于一种状态时测量时间的与MSC的定时器相比,时钟单调递增。他们以同样的速度这样做。 如果X是一组时钟,则时钟赋值是一个函数v:X→T。 vals(X)是固定X的所有时钟估值的集合。假设转换是瞬时的,但它可以重置任何时钟子集。此外,每个转换都受到时钟估值要求的保护,并且只有在满足此要求时才在语法上,一个保护是一个基本保护的合取,形式为x<$c或<$x<$c,其中x∈X,<且c∈P。给定一组时钟X,guards(X)是所有可能的警卫在X的时钟。对于v∈vals(X)和γ∈guards(X),我们定义语义关系v|=γinastraightforwardw. 解脂耶Σ为了我们的目的,时间自动机是一个结构T:=Q,X, Q,0,δ,Q,0,其中Q是状态的有限集合,起始状态q为0,结束状态的集合Q为0。X是输入字母表,X是一组有限的时钟。 的有限转移关系为δ<$Q×<$N×P(X)×guards(X)×Q,其中(q1,<$N,Y,γ,q2)∈δ意味着,给定当前时钟值v,如果v=γ,自动机可以从状态q1到q2读取<$N,并且之后时钟估值是v[Y /0]。[8]在任何状态q1下,自动机可以让任何时间流逝。好吧,让我来吧。ove.我们用一个自动机(一个有限的机器跃迁系统)A(T):=Q × vals(X),λ ∈T,(q0,λx. 0),δJ,Q×vals(X)通过如下定义转换关系δJ来接受定时词:δJ:={((q1,v1),θ,(q2,v1 [Y/0])):θγ。((q1,n,Y,γ,q2)∈ δ n v1|= γ)}<${((q1,v1),r,(q1,v1+ r)):r ∈ T}.(Forv:M→T,r∈T设v+r=λx,v(x)+r.)A(T)识别单词wfrom(q,v),i[8]因此,Y中的任何时钟都被重置,而其他任何时钟保持不变:对于任何函数,[X/α]是将α赋给任何x∈X的函数,否则其行为完全类似于,i。e. λ [X/α] = λx。(x∈X?α:α(x))。卢卡斯172=|不∈ ∈ E∈不t1t2wεtt ε和q∈Qε或•w= w1w,(q,v)→t1(q,vJ)→w1(qJ,vJJ)和w 从(qJ,V J)中识别,其中tJJ=(tJ1 − t1)(tJ2 − t1). (tj|− t1)。T的语义被定义为A(T)从(q0,λx)中识别的时间词的集合。0)。为了分析这种无限状态设备,通常将其转换为有限区域自动机。这是可能的,因为T中的跃迁数是有限的,因此在保护中使用的常数数是有界的。这使得我们在对常数(都是有理定义的)进行离散化之后,只考虑有限个时钟区域。有关此技术的更详细说明,请参见[1]。5将HMSC转换为自动机5.1不定时案件我们将定义的自动机使用在一个过程中发生的MSC的切割。就像它的配置一样。显然,我们会得到任何包含循环的HMSC的有限自动机。所以,首先我们定义一个无限转换系统,识别HMSC的语义然后,我们在节点上定义一个等价 最后,我们将证明这种等价关系只有收敛HMSC的等价类的数量有限,并以这种方式获得有限自动机:如前所述,有一些HMSC具有不规则语义,因此我们不能期望将所有HMSC转换为有限自动机。我们固定了一个HMSCH. H的配置是一对(h,n),其中(i) h是被访问节点的序列(h= h1. H|H|∈N+),(ii) 是访问事件的序列(=1. ϕ|H|,对于任意的k(j),满足k(j ∈ K(M h j)).e(n):=j1|ϕ|你好所有构形的集合是K(H)。注意,不能唯一标识h,因为允许v=。现在我们在K(H)上定义一个自然后继关系。 对于(h,n)K(H),(hJ,nJ)K(H)是(h,n)的一个9e-后继者,对于某个e,如果下列之一成立:(1) · hJ=h·l/= h对于某个h|H|l∈游程(H,h|H|,l|L|),• 吉吉|={e},对于g≤,|H|,则g = |H|的自动机.现在,自动机的状态不仅包括配置,而且还包括标记。这些标记告诉我们未来必须满足的时钟要求。 对于任何一对事件(e1,e2),我们引入一个时钟xe1,e2,如果(e1,e2)的标记被设置,则在发生e1转换时设置该时钟,并在发生e[11]类似的推理也被用于标记正在运行的动作和每个进程的时钟。12标记的设置和删除根据关于>-semantics从M到N的部分函数的集合用[M−−·N]表示。 如果f(m)对于某个m M和f[M−−·N]是未定义的,我们写f(m)=。这样一个部分函数将被用作定时器的标记(定时器T是否在运行?是的,i(T)/=.)作为一种记忆,[10]通过允许黑洞和白洞在运行过程中加入它们,图11假设e21,e1/1和τ(e1,e2)=[1,). 因为最初的时钟估值xe1,e2到0,如果我们错误地检查x e 1,e 2,我们将不能在运行的第一个时间单位内接受e 2。12我们每个进程只需要一个时钟,因为在任何进程上最多只能运行一个动作。给定的过程,但更多的标记,因为动作可能有不同的持续时间。卢卡斯175不∗∗\{∈E}{∈ E} \{}定时器已设置(到T)。我们可以用其他方法代替[−−·range()];选择部分函数是为了使定义简单。端节点的集合由与非定时情形中相同的对配置的限制来定义,但另外我们必须确保对于某个T∈T不存在T这是由部分函数控制的。设H是收敛的HMSC,.Σffi(H)=:C,E,δ,c0,Cθ是识别ΦH)0的有限自动机。 我们将其定义为:TA.哪里ΣCJ,X,E,cJ0,δJ,CJ,• CJ=C×((r(E × E))× A)×[T−−·range()];• CJ=C×((r(E × E))× A)×[T−−·];• cJ0=(c0,n,n);• X={xe1,e2:e1,e2∈E}<${xT:T∈T}<${xp:p∈P},• 对于任意变迁δ(s,e)=sj,其中e∈E和任意W∈(r(E2))× r(A))和T−−·range(λ),δJ包含((s,W,λ),e,γ,λ,(SJ,WJ,λJ)),其中A=((e∈,e)∈Wxe∈,e∈τ(eJ,e))<$xo(e)>τ(A),γ={xe,e<$ :eJ∈E},WJ=((W(eJ,e):eJ)((e,eJ):eJ))一(我们假设A是W的唯一元素,其中o(A)=o(e),并理解{A}=0,如果它不存在),而且它成立:· 若σ(e)=IT,则将γ推广到γ<${xT},若<$(T)/=<$,则将<$j推广到<$$> xT <$(T),并设<$J:=<$[{T}/<$(e)];· 若σ(e)=CT,则必须定义T,我们将T推广到T,并设T:=T[{T}/T];· 若σ(e)=OT,则必须定义σ(T),我们将σ推广到σxT=σ(T),并设σJ:=σ[{T}/σ];· 如果e∈A,则我们将γ扩展到γ<${xo(e)},将WJ扩展到WJ<${A},并设置在所有其他情况下,J=。 δJ不包含任何其他内容。很明显,一般来说,我们需要的时钟和标记要少得多。例如,如果τ(e,EJ)=P,我们就不需要考虑这一点。在下面的例子中,我们已经释放了所有无用的时钟和标记的自动机定理5.3对于收敛的HMSC H,fh>(H)只有有限个状态,并且识别fh>(H)>。同样,证明是相当技术性的,没有提供新的见解。作为一个例子,假设我们想要对以下场景建模。• 涉及两个过程,p和q。• P向Q发送消息并等待10个时间单位的应答。J=卢卡斯176∗• q最多需要2个单位才能将答案发送给p。• 如果p及时得到答案,则通信完成。如果不是那p执行某个动作(e. G.查找一些脚本)来决定是否它应该再次尝试(这需要1个时间单位),然后通信再次开始或结束。图7中给出的HMSC捕捉到了这种规范,其中我们假设异步级联。如果我们认为消息2和消息3是等价的(正如非正式规范所建议的那样),我们必须在π中处理这一点。唯一需要在视觉表示之外给出的规范部分是τ(r1,s2)=τ(r1,s3)=[0, 2]。图8给出了如上构造的自动机。 一个国家由四个组成部分。前两个组成部分是配置,即。e. B的状态我们并不把事件描述成一系列的集合,而是描述成一系列的事件,为了便于表达,我们用一个完整的切割来表示。第三个组件保存标记,第四个组件是计时器函数的图形。对于TA来说,转换是以通常的方式给出的:事件旁边是守卫,如果它不是简单的TRUE。在箭头的另一边,我们列出了要重置的时钟通常,发送和接收事件表示为si,rj,此外,动作由其标签表示,定时器事件由其类型表示。图7具有定时扩展M2M1M3M1M2M33×TQp6结论在本文中,我们看到了一种统一的方法来定义HMSC的各种语义。我们确实基于偏序的线性化定义了定时和非定时HMSC的语义,并将HMSC转换为具有等效语义的转换系统。此外,我们将收敛性确定为语义正则性的充分标准
下载后可阅读完整内容,剩余1页未读,立即下载
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](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)