没有合适的资源?快使用搜索试试~ 我知道了~
基于组合失效的约束自动机的操作语义及其在模型检查验证中的应用
理论计算机科学电子笔记250(2009)105-122www.elsevier.com/locate/entcs基于组合失效的约束自动机Mohammad Izadi伊朗德黑兰谢里夫理工大学计算机工程系人文和文化研究研究所,伊朗德黑兰Leiden Institute of Advanced Computer Science(LIACS),Leiden University,荷兰。Ali Movaghar2伊朗德黑兰谢里夫理工大学计算机工程系摘要REO是一种协调语言,用于对基于组件的计算系统的组件连接器进行建模。约束自动机作为有限自动机的一种扩展,被提出来作为Reo的操作语义。本文给出了约束自动机的一个扩展定义,每个约束自动机都可以看作是一个标号变迁系统,每个标号变迁系统都可以转化为一个约束自动机。我们表明,基于故障的等价CFFD和NDFD的同余组合的约束自动机使用其连接(生产)和隐藏操作。基于这些一致性结果,并考虑CFFD和NDFD等价的时序逻辑保持特性,它们可以用于在进行基于模型检查的验证之前减小模型的大小。关键词:约束自动机,基于故障的等价,基于故障的系统,组合模型检测,基于等价的约简。1引言基于构件的系统,特别是基于构件的软件,是一种解决大规模计算系统设计复杂性的哲学或思维方式。这种方法的主要目标之一是通过一些粘合代码来组合可重用组件。这些组件的组成模式或方式称为协调模式。有时,有一些正式的或编程语言用于指定协调模型。这种语言被称为协调语言。玲央作为1 电子邮件地址:Izadi@ce.sharif.edu2电子邮件:Movaghar@sharif.edu1571-0661 © 2009 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2009.08.008106M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105最近提出的协调语言是一种基于通道的外生协调语言,其中复杂的协调器是由简单的协调器组成的[1,3,2]。通过使用Reo规范,复杂的组件连接器可以组织在通道网络中,并以组合方式构建。Reo依赖于一个非常自由和简单的通道概念,可以模拟任何类型的点对点通信。Reo网络中使用的通道可以被认为是简单的通信过程,对它们的唯一要求是通道应该有两端(或I/O接口),声明为sink或source端,以及用户定义的语义。在源端,数据项通过执行相应的写操作进入通道。通过执行相应的读操作,在宿端从信道接收数据项Reo允许使用用户定义语义的开放式通道类型集如果我们希望能够推理规范的属性或验证其正确性,Reo以及任何其他过程规范语言都应该被赋予抽象语义。一般来说,当最终目的是推理或验证规范的属性时,语言是由某种过渡系统建模的。标记转换系统和自动机是这些语义模型的例子。在给一个特定语言一个语义模型的时候,关键的问题是:“我们什么时候可以说两个特定语言或两个模型是等价的?”在过程代数的文献中,已经提出了基于模型的过渡系统的不同等价关系的许多定义,tomata理论和并发理论。 迹等价(自动机理论等价)、Milner [14]提出的弱双相似性和Hoare [ 10 ]提出的基于故障的等价(类CSP等价)是这些等价的示例。我们说等价关系R1比R2强,如果两个模型关于R1等价,它们关于R2也等价。等价关系R1和R2是不可比的,如果R1不强于R2,R2也不强于R1。验证方法的主要目标是试图确定一个实际的系统或程序满足其要求。在形式验证方法中,人们试图通过使用数学模型描述系统来实现这一目标,将需求表示为该模型的属性,并通过严格的数学推理来表明系统的模型确实具有所需的属性[6,13]。如果形式化建模的计算系统的正确性要求以数学概念给出,例如线性或分支时间时态逻辑或无限对象上的自动机,称为模型的算法模型理论过程检查[6]可以用来检查系统是否遵守其正确性要求。模型检查已被证明是一种有效且易于使用的计算机系统验证技术。然而,使用穷举模型检查有一个主要缺点:系统的模型往往非常大。在文献中,这个问题通常被称为状态爆炸问题。在过去的二十年里,已经提出了许多方法来减少为回答某些验证或分析问题而需要构造的状态的数量。这种增强的状态空间方法实质上增加了M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105107可以验证的系统的大小,同时保留了模型检查验证方法的大部分优点。组合验证及其特例、基于等价的组合约简[12,16]、代表的偏序约简[15]、预序约简[9]、抽象[5]和使用对称性质[8]是处理状态爆炸问题的主要方法在系统的组合验证中,人们试图从其组成模块的属性中验证系统的属性[6,7,16]。一般来说,compo-当模型自然可分解时,可以更有效地利用位置验证[17]。在基于等效的成分约简方法中,在建立完整系统的模型之前,系统的组分相对于等效关系进行约简[9,6,11]。为了在基于等价的组合归约方法中有用,等价关系应该具有两个属性:它应该保持要验证的属性类,并且它应该是关于用于组合组合的语法运算符的同余。模型 通过同余关系,我们的意思是, 一个等价的模型总是产生一个与原始模型等价的模型。幸运的是,在CCS和LOTOS等流程描述语言的基于组合故障的语义模型的上下文中,有两个等价关系,由Valmari等人引入并称为CFFD和NDFD,它们具有保留属性:CFFD等价保留线性时间时态逻辑的片段,该片段没有下一次运算符并具有区分死锁的额外运算符[19,20],NDFD等价保留线性时间时态逻辑而没有下一次运算符[12]。CFFD和NDFD是保持上述线性时序逻辑片段的最小等价。在[20]中,还表明,如果我们使用标记转换系统作为语义模型,CFFD和NDFD是关于LOTOS中定义的所有复合算子约束自动机作为有限自动机或Buchi自动机的扩展,是为了捕获Reo的操作语义而提出的一种形式化[4]。在约束自动机中,与有限自动机和标记转换系统相反,转换的标签不是简单的字符或动作名称。转换标签包含一组名称和一个(约束)命题。名称集合表示参与转换的端口的名称,命题表示关于端口数据的某些约束。在[4]中,约束自动机被定义为Reo的语义模型,并且给出了约束自动机的基于迹和基于弱模拟的等价关系。在本文中,我们感兴趣的是调查基于故障的等价CFFD和NDFD的约束自动机和他们的叠合相对于组合操作,这是有用的组成Reo规格。本文的最终目标是准备一个环境的组合模型检查的约束自动机建模的Reo规格使用基于等价的约简方法。为此,我们引入了约束自动机的一个扩展定义,由此每个约束自动机都可以被认为是108M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105τ一个标记的转移系统和每个标记的转移系统可以被转换成一个约束自动机。此外,我们引入了两个新的约束自动机复合算子:两个自动机关于它们公共端口名的连接(产生)以及在自动机的所有转换标签中隐藏端口名。我们证明了基于故障的等价CFFD和NDFD对于约束自动机的连接和隐藏算子是全等的(见4.1和4.2小节)。基于这些一致性结果,并且由于CFFD和NDFD等价的线性时间时态逻辑保持特性及其极小性特性(在[12]中证明),它们将在未来的工作中用于模型检测领域的模型组合约简。第二节定义了标号变换系的概念,给出了标号变换系的复合算子和两个等价关系CFFD和NDFD。在第三节中,我们简要介绍了传统的定义,约束自动机然后,我们提出了一个新的定义的约束自动机,每个标记的转换系统可以转换为一个约束自动机,反之亦然。此外,在本节中,我们将为定义的约束自动机引入两个复合运算符:连接(产生式)和隐藏。在第四节中,我们证明了CFFD和NDFD-等价是关于约束自动机的连接和隐藏的同余。在第五节中,我们总结并讨论了一些关于这项工作的结果。2基本概念和基本定义在本节中,我们定义了标记转移系统的概念,并基于介绍它们的论文[19,20,12]介绍了CFFD和NDFD-等价关系。定义2.1转移字母表是不包含空转移标签τ的可数无限集合τ。我们把{τ}写成τ,把(ω)写成由的元素组成的所有有限(无限)词的集合符号τ用于表示空洞的词。如果σ∈(ω),则vis(σ)用于表示通过以下方式获得的词:τ τ从σ中去掉所有的τ-符号,则Σ(σ)表示σ的元素集。标记的转移系统(lts)是一个三元组L=(S,s,Δ),其中S是状态集,s∈S是初始状态,ΔεS× ετ×S是转移关系.L 的字母表,<$(L)是以下集合:<$(L)={l ∈<$|s,SJ:(s,l,SJ)∈ Δ}. 任何lts的字母表都必须是有限的。现在,我们回顾进程代数的一些基本概念,并给出CFFD和NDFD-等价的定义关于这些等价性和它们背后的直觉的更详细的讨论见[19,20,12]。定义2.2设L=(S,s,Δ)是一个标号迁移系统(lts)。如果ρ∈ε,我们写sρ0−→ sn对于n = |ρ|i Sρ n−1 使得对于所有ρ00,(s,ρ,s)∈ Δ。如果τ0 −→12i−1i iσ∈(ωσ<$σ<$)iheisaρ∈(<$$><$ω)suchhat我们写s0=sn(s0=τ τM. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105109σστσJJaσJa≈≈ρ ρs0−→ sn,(s0−→)和σ = vis(ρ)。- σ∈Σ∗是Lis =的迹。 tr(L)是L的所有迹的集合。- σ∈Σω是无限迹is=。inf tr(L)是L的所有无限迹的集合。- σ∈<$$>是Li <$的发散迹,存在ρ∈<$ωσ=vis(ρ)。 divtr(L)是L的所有发散迹的集合。ρ这样,s−→和- sJ∈Sisstablee,ifnotsJ−τ→. 如果初始状态稳定,则LtsLisstableit 如果L是稳定的,我们写stable(L),如果不是,写<$stable(L- (σ,A)∈Σ ∈σ× 2Σ,其中2Σ表示Σ的幂集,是Li σ的失败是一个sJ∈S使得s = εs且εa ∈ A。(s= 0)。- (σ,A)∈Σ ∈σ× 2Σ是Li的稳定失效,且存在稳定的SJ∈S使得s=sJa ∈ A. (s= 0)。 sfail(L)是L的所有稳定失效的集合。- (σ,A)∈Σ ∈λ× 2λ是L的非发散失败,i λ(σ,A)是失败,σ不是发散迹线 ndf ail(L)是L的所有非发散失效的集合。- (σ,A)∈×2是Li(σ,A)的发散掩盖失效或σ是发散迹.df ail(L)是L的发散屏蔽失效的集合。- σ∈εε是死锁迹 i ε(σ,ε)是L的稳定失效. dtr(L)是L的所有死锁跟踪的集合。- σ∈εε是 L的一个非发散死锁迹i ε(σ,ε)是L的一个非发散失败. nddtr(L)是L的所有非发散死锁跟踪的集合。注意,nddtr(L)=dtr(L)−divtr(L)。- L的所有非导函数的集合为:dt(L)={σ|(σ,σ)∈ndfall(L)}.下面的命题列出了这些定义的一些结果,供以后使用(证明见[20])。命题2.3设L为lts。a) t r(L)=divtr(L)<${σ|(σ,<$)∈s fa il(L)}=divtr(L)<${σ|(σ,σ)∈ndfall(L)}.b)t r(L)={σ|(σ,ε)∈fail(L)}={σ|(σ,σ)∈dfall(L)}.c) ndfail(L)= sfail(L)−(divtr(L)×2 π)。d) dfail(L)= sfail(L)<$(divtr(L)× 2 <$)。e) tr(L)= divtr(L)r(L)。f) divtr(L)n dt r(L)=。g) 如果L是有限的,那么,inftr(L)={ω ∈ <$ω| <$σ∈ <$<$:(σ是ω → σ ∈ tr(L)的真前缀)}.基于上述定义和命题,等价概念可以很容易地被定义。定义2.4(i)设L和LJ为ltss。我们说L和LJ是CFFD等价的,记为LcffdLJi可稳定的(L)惠稳定的(LJ)和divtr(L)= divtr(LJ)和inftr(L)= inftr(LJ)和sfail(L)= sfail(LJ).(ii)设L和LJ为ltss。 我们说L和LJ是NDFD等价的,并写为Lndf dLJi可调稳定(L)惠稳定(LJ)和divtr(L)= divtr(LJ)和inf tr(L)= inf tr(LJ)和ndfail(L)= ndf ail(LJ)。NDFD-等价严格弱于CFFD-等价110M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105≈≈以下定理[20]:命题2.5如果LcffdLJ,则Lndf d LJ。如果所考察的标号转移系统是有限的,则上述定义中的分量inftr是超连续的。这对应于[19]中CFFD-等价的原始定义,其中仅考虑有限lts此外,可以证明在NDFD等价的定义中可以用df ail(L)代替ndf ail(L)[20]。因此,我们有:命题2.6设L和LJ是两个有限的lts。非洲发展共同体1- LJ J J其中,i =divtr(L),且sfail(L)=divtr(L)。sfail(LJ).全国民主联盟2- LJ J J其中, f(L)=divtr(L),且f(L)=dfail(LJ).如果两个系统或进程A和B是CFFD等价的,那么直观的含义是两者具有相同的计算序列,并且此外,A可以在一系列动作之后死锁,当且仅当B也可以在相同的动作之后死锁。此外,导致发散的计算序列(内部动作的无限序列)对于两个过程是相同的定义2.7lts之间的等价关系是关于语法运算符f i {\displaystyle f i}对于每个L1,.,Ln和LJ,.,LJ,使得Li≠LJ,1ni以下成立:f(L1,. ,Ln)f(LJ,. ,LJ)。1N在[20,12]中已经证明,CFFD和NDFD等价是关于为基本LOTOS和CSP的基于标记迁移系统的语义定义的复合算子的同余。在本文的其余部分,我们investi-门的合同,这些等价的约束自动机的复合算子。3约束自动机约束自动机已经被引入作为Reo规范的操作语义[4]。在本节中,在对Reo进行简短回顾之后,我们提出了约束自动机的原始定义(作为时间数据流语言的接受者,在[4]中提出)。然后,我们引入了一个扩展的定义,使它们可以被认为是标记的转换系统,每个标签transi- tion系统可以转换为一个约束自动机。 此外,在本节中,我们将为我们定义的约束自动机引入两个复合运算符:两个约束自动机关于它们的公共端口名称的连接(产生)以及从约束自动机的所有转换标签中隐藏名称有关Reo规范语言和约束自动机作为其语义模型的更多信息,请参见[1,3,2,4]M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105111Fig. 1. Reo中的基本通道类型3.1Reo及其操作语义Reo是一种基于通道演算的外生协调语言[1,2,4]。通过使用Reo规范,复杂的组件连接器可以组织在通道网络中,并以组合方式构建。Reo依赖于一个非常自由和简单的通道概念,可以模拟任何类型的点对点通信。Reo网络中使用的通道的唯一要求是通道应该有两个通道端,声明为sink或source端,以及用户定义的语义。在源端,数据项通过执行相应的写操作进入通道.通过执行相应的读取操作,在信道的接收端从信道接收数据项。已经证明,图1中通过其图形表示示出的通道类型的集合是通道的表达完整的集合[1]。复杂的连接器有一个图形表示,称为Reo电路或网络。Reo网络的节点代表通道末端的集合它们通过Reo的连接运算符产生根据在节点A上重合的所有信道端是否是源端(则A是源节点)、汇端(则A是汇节点)或A是否组合汇端和源端(则A是混合节点),将信道分为源、汇和混合节点。源节点和汇聚节点表示组件可能连接到网络的输入和输出端口。混合节点充当路由器,其中数据项可以通过网络传输。有关Reo网络及其示例的更多信息,请参见[1,2,3,4]。现在,我们可以引入约束自动机的原始定义作为Reo的语义模型[4]。定义3.1设N是一组端口名,Data是一组数据。在名称集合N和数据集合Data上的数据约束g是一个命题,它可以通过使用以下语法来构造:G::= true|dA= d|g1和g2|gd∈数据,A∈ N我们使用DC(N,Data)作为名称集N和数据集Data上的所有数据约束的集合,由上述语法定义定义3.2约束自动机是一个四元组C=(Q,Names,T,Q0),其中,Q是有限状态集,Names是有限名称集,Q0<$Q是初始状态集,T<$Q×2Names×DC(Names,Data)×Q是C的转换集。如果(p,N,g,q)∈T,我们称N为名集,g为转移的保护。需要Ni =N且g∈DC(N,Data)。约束自动机C是有限的,条件是集合Q、T和Data是有限的。约束自动机的直观操作行为如下。它从初始状态q开始。如果当前状态为q,则C等待直到数据112M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105图二. Reo中一些基本通道的约束自动机项出现在其一些端口A1,...,An. 假设数据项d1出现在A1,数据项d2出现在A2,而(此时)在其他端口A3,. An.这触发自动机检查具有名称集{A1,A2}的状态q的传出转换的数据约束以选择转换t,使得它的保护满足A1<$→d1和A2<$→d2,导致状态p。如果没有{A1,A2}-从q的转换,其数据约束被满足,然后C拒绝。图2显示了Reo中一些基本通道的约束自动机。定义3.2是约束自动机的原始定义(在[4]中提出)。在本文中,我们将使用约束自动机的修改后的定义(例如它将在定义3.3中定义)。因此,我们有时会将定义3.2中定义的自动机称为传统的约束自动机。3.2作为标号迁移系统的约束自动机约束自动机,如在[4]中提出的,被用作基于组件的系统的组件连接器基于组件的系统包含组件和连接器。如果我们考虑整个系统,我们需要对组件和连接器进行建模和组合。基本上,组件可以通过标记的过渡系统建模。因此,我们需要找到一种方法来组合约束自动机和标记转换系统。为了这个目的,我们可以推广约束自动机的定义,使得我们可以将其视为标记转移系统,并且也可以将标记转移系统转化为约束自动机。在这一节中,我们研究了约束自动机和标记转换系统之间的双向我们引入了约束自动机的修改定义,其中,转换可以由内部或外部动作标记。外部作用如传统定义3.2所定义。内部作用量由跃迁上的τ标记引入。使用这个定义,每个约束自动机可以被认为是一个标记的转换系统,每个标记的转换系统可以简单地转换为一个约束自动机。此外,在本节中,我们将介绍两个使用新定义的约束自动机的复合运算符:两个约束自动机关于其公共端口名的产生(连接)和端口名的隐藏。M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105113−→约束自动机我们证明了在第2节中介绍的CFFD和NDFD等价是关于这些复合算子的同余定义3.3假设数据是一组数据。 一个约束自动机是一个四元组C=(Q,Nam,T,q0 ) , 其 中 Q 是 一 个 有 限 的 状 态 集 , Nam 是 一 个 有 限 的 名 称 集 , T<$Q×(2Nam×DC(Nam,Data))×Q是转换关系,q0∈Q是初始状态。N,g我们写p−→q而不是(p,N,g,q)∈T,并称N为名集,g为保护过渡时期。对于每个(p,N,g,q)∈T,要求g∈DC(N,Data)。NotettDC(t,Data) ={t ru e,fa ls e}. 我们使用τasa shorthady molforthetransitionlabel(t,true). 在这里,p−τ→q的过程是一个过程,而q是一个过程。我们对约束自动机的定义与它的原始定义(在[4]中定义)的主要区别是:1-在新的定义中,τ−transition是允许的,而在它的原始定义中是不允许的。我们需要τ-transition是因为两个原因:第一,τ-transition可以用作实际系统中发生的每种内部动作的符号,但它的真实类型在约束自动机建模中并不重要,第二,隐藏算子可以隐藏一个transition的所有port-names。在这种情况下,我们用τ代替跃迁标签。 2-我们假设一个约束自动机的初始状态是唯一的,因为允许τ-转换。 我们可以通过使用一个唯一的初始状态和从它到其他可能的初始状态的τ-跃迁3-我们的约束自动机的定义通过放弃所有运行必须是无限的要求而与原始的定义不同。我们还处理finite run,这是讨论死锁配置所必需的显然,如果我们考虑定义3.3中定义的约束自动机,每个标记的转换系统都可以转换为约束自动机。为了这个目标,我们应该通过使用τ−转换来保存内部动作,而对于外部动作,我们应该确定它们的(输入或输出)端口名称和约束(if是必要的)。另一方面,每个约束自动机可以被认为是一个具有字母表n ={(N,g)|NNamg ∈DC(N,Data)<$N <$}。因此,在本发明中,命题3.4设C =(Q,Nam,T,q0)是数据集数据上的约束自动机,如定义3.3中所定义的。C可以被认为是在字母表A上的ltsL =(S,s,Δ),例如在定义2.1中定义的,其中,S=Q,s=q0,n ={(N,g)|N<$Nam<$g∈DC(N,Data)<$N/=<$},(qi,(N,g),qj)∈Δ惠(qi,N,g,qj)∈T且(qi,τ,qj)∈Δ惠(qi,τ,qj)∈T.基于命题3.4,约束自动机的迹和失败的定义将与定义2.2中的定义相同。3.3组合约束自动机由于约束自动机旨在捕获Reo的操作语义,因此我们需要两个组合操作符来组合或重构它们:两个约束自动机关于其公共端口名称的产生(连接)114M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105以及对约束自动机隐藏端口名称在本节中,我们使用约束自动机的新定义来给出这两个复合算子的定义这些定义是其原始对应物的推广,并保存了[4]中为它们证明的所有性质。定义3.5设C1=(Q1,Nam1,T1,q01)和C2=(Q2,Nam2,T2,q02)是两个约束自动机 。 C1 和 C2 的 乘 积 ( 连 接 ) 约 束 自 动 机 是 : C1Da C2= ( Q1×Q2 ,Nam1×Nam2,T,q01×q02)其中,T定义如下:1)If(q1,N1,g1,p1)∈T1,(q2,N2,g2,p2)∈T2,N1/=n,N2ndN1<$Nam2=N2<$Nam1,则(q1,q2>,N1<$N2,g1<$g2,p1,p2>)∈T,<2) 设f(q,N,g,p)∈T1且N ndN<$Nam2=n,then,(q,qJ>,N,g,p,qJ>)∈T,3) If(q,N,g,p)∈T2andndN<$Nam1=n,then,(,N,g, )∈T.由于乘积的上述定义是其原始对应部分的推广,如果我们将约束自动机的语言字母表限制为其可观察元素(将所有形式为(N,g)的转换标签视为可观察的,并忽略所有单词中的τ),则它保存了[4]中为其对应部分所示的所有性质。定义3.6设C=(Q,Nam,T,q0)是一个约束自动机,B是一个名字,B∈Nam。将B隐藏在A中所产生的约束自动机是[C] =(Q,Nam\{B},T<$B,q0)其中,T定义如下:(1) 若(q,N,g,p)∈T且N/=N,则(q,N\{B},N\{B}[g],p)∈T<$B,其中B[g]=(2) 若(q,τ,p)∈T,则(q,τ,p)∈T<$B.除了上面的两个复合算子,基于命题3.4,我们可以使用任何其他定义良好的复合算子来组合约束自动机,这些复合算子是为标签转换系统定义的。4一致性结果在这一节中,我们研究了CFFD和NDFD等价关系关于约束自动机的连接(产生式)和隐藏组合的一致性本节包含两个部分,第一部分我们考虑连接运算符(定义见定义3.5),另一部分我们考虑隐藏运算符(定义见定义3.6)。4.1CFFD和NDFD是关于约束自动机的连接的同余在本节中,我们证明等价CFFD和NDFD是关于有限约束自动机的产生(连接)的同余,如定义3.5所定义。我们的证明方法非常类似于CFFD和NDFD等价的作者用来证明他们关于[20]中定义的复合算子的同余的方法。首先,我们定义了一个谓词Join(σ;π,ρ),它直观地意味着词π和ρ可以被看作是两个约束自动机的迹,而词σ可以被看作是乘积(join)约束自动机的迹M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105115使得σ是ρ和π的乘积。然后,我们证明了乘积自动机的所有迹、所有稳定故障、所有发散迹和所有发散屏蔽故障的集合都可以由它们在两个约束自动机中的对应物来表征(见命题4.2)。基于这些特征,我们将证明同余。因为我们的最终目标是在模型检查的上下文中使用等价性,所以我们将证明有限约束自动机的同余定义4.1设Data是一组有限的数据,Nam1和Nam2是两个有限组的名字。设{(N,g)|NN1N=/n ={(N,g)|NNam2<$N/=<$g∈DC(N,Data)},{n∈DC(N,Data)},n ={(N,g)|NNam1Nam2N/= g∈DC(N,Data)},以及σ =(N1,g1)(N2,g2). 是字母表上的单词。 谓词Join(σ;π,ρ)成立(为真)当且仅当以下过程可以从σ,成功:1- 定义一个从{1,2,3,.. . }到{2- 从σ得到π2-1-对于所有i≥1,将(i)=2-2-移除所有从σ移动(i)=“第二“的(Ni,gi)3-从σ得到ρ3-1-对于所有i≥1,将(i)=3-2-移除从σ移动(i)=“first“的所有(Ni,gi)我们用g[Nami]表示命题g对名称集合Nami的限制:它可以通过从g的合取范式中删除所有包含dA=d的项来获得,其中A/∈Nami。显然,如果上述过程可以成功地获得单词π和ρ,则π将是字母表π1上的单词,ρ将是字母表π2上的单词。命题4.2设C1 =(Q1,Nam1,T1,q01)和C2 =(Q2,Nam2,T2,q02)是两个有限约束自动机.设C = C1Da C2, 则,(i)tr(C)={σ |<$π ∈ tr(C1),<$ρ ∈ tr(C2),Join(σ; π,ρ)}.(ii) sfail(C)= {(σ,A)|<$(π,B)∈sfail(C1),<$(ρ,D)∈sfail(C2),Join(σ; π,ρ)<$A<$G<$B<$D<$A<$GJ <$B<$D},其中,G={(N,g)|N<$Nam1<$Nam2<$N < $$>(N<$Nam1=< $ $ >N<$Nam2=<$)},GJ={(N,g)|N<$Nam1<$Nam2<$N=/(N<$Nam1/= N <$Nam2(iii) 稳定(C)=稳定(C1)不稳定(C2)。{\fnSimHei\bord1\shad1\pos(200,288)}(ix) divtr(C)= {σ| ∃π∈tr (C1),∃ρ∈tr (C2),Join (σ; π, ρ) and (π∈divtr (C1) ∨ρ∈ divtr(C2))}.(x) df ail(C)= {(σ,A)|<$(π,B)∈df ail(C1),<$(ρ,D)∈df ail(C2),Join(σ; π,ρ)<$A<$G<$B<$D<$A<$GJ <$B<$D}<$(divtr(C1Da C2)×2<$),其中,<$是116M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105≈CQC我的天 然后,C Da DCQC D aD.CQC我的天然后,C D aDCQCD aD.与定义4.1中的定义相同,并且G和GJ与(ii)中的定义相同证据 参见附录A和Q命题4.3设C和CJ是同一名称集上的有限约束自动机,D和DJ是同一名称集上的有限约束自动机非洲发展共同体CJ法国外交部cffdJ J证据 (i)根据命题4.2(iii),稳定(C D a D)=稳定(C)不稳定(D)。非洲发展共同体由于CCJ DcffdDJ,我们有,stable(C)=stable(CJ),稳定(D)=稳定(DJ)。因此,stable(CD a D)=stable(CJDa DJ)。(ii) 根据第4.2(ii)条,sfail(C D a D)={(σ,A)|<$(π,B)∈sfail(C),<$(ρ,E)∈sfail(D),Join(σ; π,ρ)<$A<$G<$B<$E<$A<$GJ<$B<$E}其中,G ={(N,g)|NNamC= NNamD=},GJ={(N,g)|南庄阮南哲陈南杰{\fn方正黑体简体\fs18\b1\bord1\shad1\3cH2F2F2F}.由于CFFD等价性sfail(C)=sfail(CJ)和sfail(D)=sfail(DJ)。由于名称集合的相等性,在CD a D的情况下,G和GJ相等其中G和GJ在CJDa sfail(CJDa DJ)的情况下。(iii) 根据第4.2(ix)号提案,J,分别。 因此,sfail(CD a D)=divtr(C D a D)={σ| <$π∈tr(C),<$ρ∈tr(D),Join(σ; π,ρ)和(π∈divtr(C)<$ρ∈divtr(D))}。基于命题2.3(a),tr(C)=divtr(C)<${σ|(σ,σ)∈s fail(C)}和CJ,D和DJ的全对称性. 由于CFFD等价性divtr(C)= divtr(CJ),divtr(D)= divtr(DJ),sfail(C)= sfail(CJ),sfail(D)= sfail(DJ)。因此,tr(C)=tr(CJ)和tr(D)=tr(DJ)。因此,divtr(CD a D)=divtr(CJDa DJ)。Q推论4.4 CFFD-等价是关于有限约束自动机的乘积(联)的 同 余 。命题4.5设C和CJ是同一名称集上的有限约束自动机,D和DJ是同一名称集上的有限约束自动机全国民主联盟CJ民族民主阵线全国民主阵线证据索赔的证明稳定(CD a D)=和D和DM. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105117稳定(CJDaDJ)和divtr(CD a D)=divtr(CJDa DJ)与命题4.3的证明相同。现在我们证明,df ail(CD a D)=df ail(CJDa DJ)。按命题 4.2(x),df ail(C D a D)={(σ,A)|<$(π,B)∈df ail(C),<$(ρ,E)∈df ail(D),Join(σ;π,ρ)和A<$G<$B<$E<$A<$GJ <$B<$E}<$(divtr(C1DaC)×2μ m)。 由于Cndf dCJ和Dndf dDJ,df ail(C)=df ail(CJ),df ail(D)=2≈ ≈并且divtr(CD a D)=divtr(CJDa DJ)。 由于平等的名称集合,在CD a D的情况下G和GJ等于在CJDa DJ,分别。因此,df ail(CD a D)=df ail(CJDa DJ)。Q118M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105B)、^B)、≈J推论4.6 NDFD-等价是关于有限约束自动机的乘积(联)的同余。4.2CFFD和NDFD是关于约束自动机隐藏的同余式在本节中,我们证明等价CFFD和NDFD是关于在定义3.6中定义的有限约束自动机中隐藏端口名称的同余。首先,我们证明了在一个约束自动机中隐藏一个端口名之后,自动机的所有迹、所有稳定故障、所有发散迹和所有发散屏蔽故障的集合可以由它们在原始约束自动机中的对应物来表征(见命题4.8)。基于这些特征,我们将证明同余。因为我们的最终目标是在模型检查的上下文中使用等价性,所以我们将证明有限约束自动机的同余。定 义 4.7 设 Nam 是 一 组 名 称 , Data 是 一 组 数 据 , n ={ ( N , g ) |N<$Nam<$g∈DC(N,Data)}和B∈Nam。我们定义了集合hideB在Σ 1中,对于每个集合hideB,对于每个单词σ =(N1,g1)(N2,g2). 使得:隐藏B在1={(N\{B},[B] g)|(N,g)∈ <$1<$N{B}N{\fn方正黑体简体\fs18\b1\bord1\shad1\3cH2F2F2F}.hideBinσ是一种将所有对都移动到form(n,g)中的方法由w或d(N1\{B},n[B]g1)(N2\{B},n[B]g2). . . .命题4.8设C =(Q,Nam,T,q0)是有限约束自动机,A=<$B [C]是B在C中隐藏所产生的约束自动机(对于B∈ Nam)。然后,(i)tr(A)= {hide B inσ|σ∈ tr(C)}.(ii) sfail(A)= {(hide B inσ,A)|(σ,A<$AJ<$^ (C)}},其中AJ={(N<${B},g)|<$gJ∈DC(N,data):(N,gJ)∈A}和B={({B},g)|g ∈ DC({B},data)}.(iii) stable(A)= stable(C)g ∈ DC({B},Data):({B},g)/∈ tr(C).(ix) divtr(A)={hide B in σ σ ∈ divtr(C)}<${hide B in σ σ ∈ inf tr(C)<$|||在σ中隐藏B| ∞<}。(x) df ail(A)= {(hide B inσ,A)|(σ,A<$AJ<$^∈df ail(C)}<$(divtr(<$B[C])×2<$),其中,在定义4.7中定义了。证据 参见附录B和Q命题4.9设C和CJ是同一组上的有限约束自动机,非洲发展共同体名称,C法国外交部C和B是名称集合中的名称。 然后,B [C]证据[C].(i) 根据命题4.8(iii),stable(B[C])=stable(C)g∈DC({B},Data):({B},g)/∈tr(C)。因为,CcffdCJ,stable(C)= stable(CJ),divtr(C)=divtr(CJ),andds fal il(C) =s fal il(CJ)。 ByProposition2. 3(a),tr(C) =divtr(C)<${(σ,<$)|σ∈sfail(C)}.因此,tr(C)= tr(CJ)。因M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105119此,stable(B[C])=stable(B[CJ])。120M. Izadi,A.Movaghar/电子笔记理论计算机科学250(2009)105B)、≈B)、CQC≈[C].^(ii) 根据提案4.8(ii),sfail(B[C])={(hideBinσ,A)|(σ,A<$AJ<$ ^∈sfail(C)}},AJ={(N<${B},g)|<$gJ∈DC(N,data):(N,gJ)∈A}^{({B},g)|g∈DC({B},data)}.,B=因为,CcffdCJ,sfail(C)= sfail(CJ)。 因为C和CJ的名称集是在C和CJ的情况下,集合AJ和B的定义相同。 因此,在本发明中,sfail(B[C])=sfail(B[CJ])。(iii) 根据命题4.8(ix),divtr(B [C])= {hideBinσ|σ∈ divtr(C)}{hideBinσ|σ∈inftr(C) ∧ |在σ中隐藏B| ∞<}。 正如我们在(i)中所示,tr(C)=tr(CJ)。根据命题2.3(g),由于C和CJ是有限的,inf tr(C)={ω∈ <$ω| <$σ∈ <$<$:
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
会员权益专享
最新资源
- BSC绩效考核指标汇总 (2).docx
- BSC资料.pdf
- BSC绩效考核指标汇总 (3).pdf
- C5000W常见问题解决方案.docx
- BSC概念 (2).pdf
- ESP8266智能家居.docx
- ESP8266智能家居.pdf
- BSC概念 HR猫猫.docx
- C5000W常见问题解决方案.pdf
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).docx
- BSC概念.docx
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).pdf
- BSC概念.pdf
- 各种智能算法的总结汇总.docx
- BSC概念 HR猫猫.pdf
- bsc概念hr猫猫.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](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)