可在www.sciencedirect.com在线获取理论计算机科学电子笔记333（2017）73-87www.elsevier.com/locate/entcs基于δ-互模拟的系统近似正确性Yanfang Ma1，2淮北师范大学中国，淮北潘海玉3号台州学院中国台州摘要系统的正确性是量化系统质量的重要属性。基于完备格的δ-互模拟是对经典互模拟的推广。为了分析系统逐步逼近其规范的实现，建立了δ互模拟的无限演化机制。首先，分析了δ-互模拟下实现与规范之间的关系，定义了δ-极限互模拟，并给出了δ-极限互模拟的实例.然后，δ-互模拟极限被提出来说明规格是实现的极限。证明了δ-互模拟极限的一些代数性质。 最后，为了使用灵活的分层开发利用模块化设计方法求极限，证明了δ-互模拟极限在各种组合子下关键词：极限，正确性，互模拟，完备格，模糊系统1介绍正确性是评价系统质量的重要指标根据进程代数理论，正确性可以描述为实现与规范之间的等价关系，如互模拟等价，1本 工 作 得 到 国 家 自 然 科 学 基 金 （ 61672023 ， 61300048） 、 安 徽 省 自 然 科 学 基 金 （ 1708085MF159 ，1508085MA14）、安徽省高校自然科学重点基金（KJ2014A223）、高校优秀青年人才基金（1999年）、安徽省高校优秀青年人才基金（1999年）、安徽省高校安徽省高等教育振兴计划（2014ZDJY058）2电子邮件：clmyf@163.com3电子邮件：phyu76@126.comhttps://doi.org/10.1016/j.entcs.2017.08.0071571-0661/© 2017由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。74Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73然而，在实际应用中，系统中存在大量的硬件设备，很难保证系统的完全等价性。对于许多系统，实现近似满足规格[1，2，3]。在Ying在静态观点中，允许系统的实现与其规范之间存在一定的小误差。在这种情况下，该系统可以被视为规范的近似实现。已经提出了许多理论来描述这种方法的近似正确性 （ 例 如 [6 ， 7 ， 8 ， 9] ） 。 这 些 理 论 的 思 想 是 推 广 等 效 的 概 念 与psedometric，旨在衡量行为之间的差异非等效模型。在系统的设计过程中，需要在开发过程中对系统的正确性进行验证。然而，很多原因会导致第一次实现不能满足规范，如程序语言和开发人员经验的不一致等。因此，实施工作应逐步改进得到了实现的演化序列。从设计的过程中，我们注意到规格是实现序列的最终目标这意味着系统在设计过程中越来越正确。为了描述这种特征，Ying提出了研究正确性的动态方法[5]。这意味着一系列实现越来越接近规范。这一系列的实现可以看作是朝着规范的演进。Ying[5]提出了强/弱极限双模拟和强/弱互模拟极限来描述系统正确性的无限演化。为了刻画环境的影响，本文的第一作者提出了参数化极限互模拟和三分之二极限互模拟[10，11]。最近，第一作者提出了确定性概率过程中的互模拟极限和互模拟极限，以表征概率系统的动态正确性[12]。为了得到系统的近似解，将行为等价推广到定量情形和极限情形。然而，这些扩展主要集中在标记迁移系统（LTS）的数值行为等价语义上，其中标记动作之间的度量真值来自实数。从偏序集的观点看，实数真值是可比较的但是，Pan等人[13，14]给出了一些例子，说明转移系统中的真值可能不是数字，也不是线性排序的。基于这种情况，他们将模拟的概念扩展到剩余格值设置[15]。首先，将标号迁移系统推广到定量迁移系统（QTS）。然后，在QTS上定义了δ-模拟，它放宽了经典模拟中标签跃迁的相等性，允许执行由不同标签引起的跃迁，只要标签之间的真度大于或等于从某个格中提取的阈值δ。自然地，我们可以实现δ-互模拟，以提供一种方便的共归纳证明技术来建立行为等价。尽管Pan等人提出的δ模拟的一些有趣的方面，Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7375Σαδ-互模拟是经典互模拟的推广，而在用δ-互模拟来验证系统的近似正确性时，系统正确性的无限演化在现实世界中，如果依赖于的系统的真值不是数字且不是线性排序的，则可以选择δ互模拟来验证系统的近似正确性。因此，我们需要描述实现的无限演化机制本文的目的是将δ-互模拟推广到δ-极限互模拟和δ-互模拟极限。此外，它们的代数性质将被讨论。第二节回顾了CCS和δ-互模拟的一些概念和结果. 在第三节中，定义了δ-极限互模拟，并给出了一些例子第四节给出了δ-互模拟极限。证明了δ-互模拟极限的唯一性及与δ-互模拟的一致性。第五节给出了各种组合子下δ-互模拟极限的替代律。最后我们在第6节结束论文2预赛2.1CCS摘要设Act= Γ{τ}为动作的集合，其中τ为无声或完美动作，Γ为标签的集合。定义l，lJ，···range over Γ。 通信和并发系统（CCS）语法的详细定义可以在[16]中找到。接下来，我们只展示过程表达式的定义定义2.1 [过程表达式][16]过程表达式集合E包括K和以下表达式：E：：=α.E|Ei|E1|E2|E\X|E[f]，i∈I其中X<$r，f：r→ r是重新标记函数，r是过程变量的集合K是过程常数的集合，I是索引集合。一般来说，我们称过程为不带变量的过程表达式的集合，用符号P表示。CCS的过渡语义在[17]中提出，这是结构化操作语义。定义2.2[标记转移系统（LTS）][16]标记转移系统σ=（E，Act，{→：α∈Act}）的转移关系→α76Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73Σ→法总和Ej→αEJJα.E→αEJi→i∈IEJJ（j∈I）E→αEJF→αFJCom1αE|F →EJ|FCom2 E|F→αE|F JCom3 E→lEJFlFJResE→αEJE|F→τ EJ|F JE\X→α（α，α<$∈/X）EJ\XRelE→αEJf（α）ConP→A→α PJdef（A=P）PJ2.2δ模拟E[f]→EJ[f]Pan等人提出了一种新的LTS扩展，称为定量迁移系统（QTS），其中标签集配备了经典等价关系的剩余格值版本为了将经典互模拟推广到剩余格上，在[15]中定义了δ-模拟。接下来，我们将回顾晶格和δ模拟的一些定义。对于格的符号，详细内容可以在文献[18]中找到。作为偏序集的格将用（L，≤）表示，而格则用代数（L，n，n）表示。有时我们简单地写L来表示两种意义上的格。根据格理论，设（L，L，L）是完备格，Y是非空集，则函数f：Y2→L是Y上的L值（格值）关系.对一个L-值关系f，如果f（x，x）=1，对所有x∈Y，则f是自反的;如果f（x，y）=f（y，x），对所有x，y∈Y，则f是对称的;如果f（x，y）<$f（y，z）≤f（x，z），对所有x，y，z∈Y，则f是传递的。通过等价关系的定义，我们知道，如果f是自反的、对称的和传递的，则Y上的L-值关系称为L-值等价Y上满足f（x，y）=1蕴涵x=y的L-值等价关系称为L-值等式关系.其次，我们将回顾数量转移系统的定义和δ-Pan等人提出的模拟[15]。定义2.3[15]一个定量跃迁系统（简称QTS）是Q=（A，θ），其中• A=（S，R，R），称为QTS的支撑集，是一个LTS，其中S是状态集，R是标号集，R是转移关系集;• θ是θ上的L-值等式关系当θ是脆的时，LTS可以看作是退化的QTS由于QTS对LTS进行了一般化，因此可以利用QTS得到过程表达式的迁移语义，从而更一般地描述系统在真值为αEαY. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7377→→标签不是数字。 转换规则与LTS相同。The d'americanQTS中的状态集是过程表达式集，标签集是Act，转移关系为→α（α∈Act），关系为L-值相等关系θ关于ACT因此，我们可以根据Pan的δ-模拟重写过程P的δ-模拟。等[15]定义2.4[δ-模拟][15]设Q=（A，θ）是一个QTS，δ∈L。的关系Sδ<$P×P称为δ-模拟，如果对任意（W，V）∈Sδ和任意α∈Act，当βW→αWJ，存在β∈Act和VVj，满足θ（α，β）≥δ和（WJ， VJ）∈Sδ.为了提供一种方便的共归纳证明技术来建立等价关系，根据δ-模拟的定义，自然可以定义δ-互模拟。定义2.5[δ-互模拟]设Q=（A，θ）是一个QTS，δ∈L. 的关系Sδ<$P × P称为δ-互模拟，如果对任意（W，V）∈ Sδ和任意α∈Act，• 若W→Sδ;β• 如果V→WJ，存在β∈Act和VβVJ，则x是tα∈Act且W→α使得θ（α，β）≥δ且（WJ，VJ）∈WJ使得θ（α，β）≥δ且（WJ，VJ）∈Sδ。通常，我们用符号W<$δV来表示W和V是δ-双相似的，如果存在δ-互模拟S使得（W，V）∈S。换句话说，δ-双相似性δ定义为{Sδ：Sδ是δ-互模拟}。3δ-极限互模拟当δ-互模拟被用作验证规范和实现之间正确性的标准时，实现可能不满足规范。为确保实现满足规范要求，必须修改实现。产生了一系列的实现对于一个简单的系统，这些实现可以形成一个序列{Wn：n∈ω}，其中ω是自然数集。在现实世界中，W1，W2，···可能不满足规范V，但存在n0∈ω使得对于任何n≥n0，Wn可以满足规范V。根据拓扑学的观点，规范V可以被视为这些实现的极限。通常，对于一个复杂的系统，它是由多个模块组成的，实现的修改可以同时由不同的模块完成。在这种情况下，修改后的实现可以形成偏序。因此，我们可以使用过程网来描述这种情况。根据Domain理论，网是从有向集到非空集的映射。进程网也是从有向集到进程集的映射。关于有向集、相关性、相关子集、网和子网的更多细节，读者可以参考文献[19，20]。α78Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73αα444一我们把P上所有网的类记为PN。 对任意{Pn：n∈D} ∈PN，其中D是有向集，对任意n∈D，Pn∈ P.现在，我们给出δ极限互模拟的定义如下。定义3.1 [δ-极限互模拟]设Q =（A，θ）是QTS，δ ∈ L，其中A =（P，Act，{→：α ∈ Act}），θ是Act上的L-值等式关系。一个关系SδP ×PN。如果（W，{Vn：n∈D}）∈Sδ对任意α∈Act满足下列条件，则Sδ称为δ-极限互模拟：• 若W→WJ，则对任意n∈D，有βn∈Act，{VNJ：n∈D} ∈PN，且βnn∈D使得对任意n≥n，VJ，θ（α，β）≥δ且（WJ，{VJ：n∈D}）∈0Sδ;n→nn0n• 如果C是D的一个闭子集，则VβmVJ对于任意m∈C，则有α∈Act，Jm→mαJW∈ P，C的一个闭子集B使得W→W，θ（α，βk）≥δ，对任意k∈B和（WJ，{Vk：k∈B}）∈S δ.与定义2.5相比，定义3.1中的关系S δP ×PN比定义2.5中的关系S δP × P更复杂。如果一个系统的规格被抽象为W，在设计过程中得到的实现被表示为{Vn：n∈D}，那么Sδ表示规格和实现之间的关系。此外，δ-极限互模拟的条件是：对任意n≥n0，W和Vn之间存在δ-互模拟关系.因此，δ-极限互模拟是δ-互模拟的推广。例3.2设P = a。0 + b。0，Q n= an. 0 + b n. 0，n∈ω.然后，过渡图如图1所示。由于（ω，≤）是一个有向集，{Qn：n∈ω} ∈PN，P∈ P. 设L =（[0，1]，≥），偏序在集合上大于等于θ是作用集上的L值等式关系，其中δ = 0. 9∈ [0，1].θ（a，a）=θ（b，b）=θ（an，an）=θ（bn，bn）= 1，θ（a，a0）= θ（b，b0）= 1× 0. 9,θ（a，a1）= θ（b，b1）= 2× 0. 9,θ（a，a2）= θ（b，b2）= 3× 0. 9、θ（a，a n）= θ（b，b n）=（n −（n − 1））× 0。9当n≥3时，除了θ的值，对于任何其他作用θ（α，β）= 0，其中αi=a或b，β ai或bi，i= 0， 1，···，n.P ×PN上的关系为Sδ={（W，{Vn：n∈ω}），（W1= 0，{Wn= 0：n∈ω}），（P2= 0，{Vn = 0：n∈ω}），（0，{ 0：b∈B}）}，其中B是ω的任意有限子集.根据定义3.1，我们可以发现Rδ是δ-极限互模拟。事实上，如果P→P1，则存在n∈Act，其中n∈ω，{QJ=Wn：n∈ n阿纳杰ω} ∈PN，且n0= 3使得Qn→Qn，对任意n≥n0，θ（a，an）≥δ，且B（0，{QJn：n∈ω}）∈Sδ. 若P→0，则存在bn∈Act，其中n∈ω，{Qjn=Vn：n∈ω} ∈PN且n0= 3suchthatQn→bn（0，{QJn：n∈ω}）∈Sδ.对任意n≥n0，Q_n，θ（b，b_n）≥ δ，Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7379M→α另一方面，如果C是ω的一个闭子集，且Qma→MQJ= 0对于任何m∈C，则我们假设C={n：l∈ω}。Q=QanlQJ每l m nlnlJm∈C.因此，存在a∈Act，P= 0，并且存在一个C={nl+4：l∈ω}的C，使得P→aPj，θ（a，ab）≥δ，其中b∈B且（PJ，{QJ：b∈B}）∈Sδ. 最后，B证明了Sδ是δ-极限互模拟。Fig. 1.δ-极限互模拟的一个例子根据δ-极限互模拟的定义，将过程间的恒等关系推广到极限情形。命题3.3设Q =（A，θ）是一个QTS，δ ∈ L. 然后，IlimSδ={（W，{Vn：n∈D}）：W∈ P，{Vn：n∈D} ∈PN，且存在n0∈D使得对任意n≥n0，Vn=W}是δ-极限互模拟。命题3.3指出，如果得到的实现在经过一些修改后与规范相同，则实现与规范之间的关系是δ-极限互模拟。接下来，我们将提供一些附带的结果，这些结果有助于描述系统的规范和实现之间的关系我们认为子网封闭的进程和网络的进程之间的关系。设Q=（A，θ）是一个QTS，δ∈L，Sδ<$P×PN.然后我们定义sub（Sδ）={W，{Vn：n∈D}）：存在（W，{Wm：m∈C}）∈Sδ使得{V n：n∈D}是{W m：m∈C}}的子网。命题3.4设Q =（A，θ）是一个QTS，δ ∈ L，S δ<$P ×PN. 则sub（S δ）是δ-极限互模拟当且仅当对（W，{Vn：n∈D}）∈Sδ和 α∈Act，• 若W→WJ，则对任意n∈D，{VNJ：n∈D} ∈PN，存在βn∈Act，且βnn∈D使得VVj，对所有n ≥ n，θ（α，β）≥δ，且（W，{V：n∈D}）∈0publicintfindDuplicate（）;80Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73n→nn0nY. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7381→Bβ也是δ-极限互模拟。i∈I• 如果C是D和Vβm VJ对于所有m∈C，则存在Jm→mαJα∈Act，W ∈ P，C的一个闭子集B使得W→W， θ（α，βk）≥δ对k ∈ B，（WJ，{Vk：k ∈ B}）∈ sub（S δ）.证据 对于“只有当”：它来自定义3.1。对于设（W，{Vn：n∈D}）∈sub（Sδ）.然后通过构造sub（Sδ），得到（W，{Wm：m∈C}）∈Sδ，使得{Vn：n∈D}是{Wm：m∈C}的子网.进一步，根据子网的定义，证明了存在映射f：D→C，使得（D，f）是C的一个闭集，且对任意n∈D，Vn=Qfn.根据Domain理论，我们可以假定映射f是增的，即n1≤ n2蕴涵f（n1）≤ f（n2）.若W→αWJ，则根据命题3.4的条件，βm对任意m∈C，{VJ：m∈C} ∈ P，且m∈C使得VVj，θ（α，β）≥δmN0J Jm→Mm对所有m ≥ m0且（W，{Vm：m ∈ C}）∈ sub（S δ）. 由于（D，f）是C的一个余性，存在一些n0∈D，其中fn≥m0，eachn≥n0. LetVnJ=WfJn，对于每个n∈D，我们有V=WβfnWJ=Vj，对于所有n≥n，其中{VJ：n∈D}是nfnfn nn0nJ J J一个子网{Wm：m∈C}。 通过构造sub（Sδ），（W，{Vn：n∈D}）∈su b（Sδ）. 因此，若W→αWJ，则对任意n∈D，存在γn=βf∈Act，nγn{VJ：n∈D} ∈ P ，n∈D使得VVJ，θ（α，γ）≥δ，对所有n≥n，nN0J Jn→nn0且（W，{Vn：n∈D}）∈sub（S δ）.如果B是D的一个闭子集，则Vb→VBJ，则f（B）是一个常数C的子集。设WJ=VJ，b∈B.然后我们就能得到那个W=VβbfbbJ JJfbb→Vb=Wfb对所有b∈B.此外，存在α∈Act，W∈ P和一个常数f（B）子集H such使得W→αWJ且（WJ，{WJ：r∈H}）∈sub（Sδ）. 由于fR是递增的，f−1（H）是B的一个闭子集。因此，我们有{WrJ：r∈H}={VbJ：b∈f−1（H）}和（WJ，{VbJ：b∈f−1（H）}）∈sub（Sδ）。Q从命题3.4，很容易得到以下推论。推论3.5设Q=（A，θ）是QTS，δ∈L.如果S δ是δ-极限互模拟，则sub（S δ）也是δ-极限互模拟。根据定义3.1，我们可以得到任何δ-极限互模拟的并集都是δ-极限互模拟。推论3.6若δ∈L，（Sδ）i是δ-极限互模拟，对每个 i∈I，则（Sδ）i4δ-互模拟极限在这一节中，我们将给出δ-互模拟极限的定义，以描述系统在δ-互模拟下的收敛机制δ-互模拟极限是系统在δ-互模拟下实现的极限，它表征了系统的具体化。82Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73δ、∈αK定义4.1设Q=（A，θ）是一个QTS，δ∈L，W∈ P，{Vn：n∈D} ∈PN.• 如果存在δ-极限，则称W∈ P为{Vn：n∈D}互模拟Sδ使得（W，{Vn：n∈D}）∈Sδ.我们可以使用符号WlimVn来表示这个极限。n∈D假设n ∈lim=，（W，{Vn：n∈D}）：W∈P，{Vn：n∈D}∈PN且W∈δlimVn，n∈D然后推论3。6.告诉我们，δlim是最大的δ-极限二进制数。下面的命题提供了δ-互模拟极限的递归机制。命题4.2（递归定义）设Q =（A，θ）是一个QTS，δ∈L。 然后WδlimVn当且仅当对于任意 αAct，n∈D(i) 若W→WJ，则存在βn∈Act，其中n∈D，{VNJ：n∈D} ∈PN，n0∈D使得Vn→αVJ和θ（α，βn）≥δ，其中n≥n0和Wj<$δLIMV J;n nn∈Dβm(ii) 若C是D的一个闭子集，对任意m∈C，Vm →Qm′，则有αα∈ Act，WJ∈ P， B是 C的一个闭子集，使得 W→WJ，θ（α，βk）≥δ，k∈B且Wj<$δlimVj.k∈B是的。对于很容易得出结论。关于KlimVn，则根据定义3.1，我们n∈DS δ={（W，{V n：n ∈D}）：对于α ∈Act，命题4.2中的条件成立}。在下文中，我们需要证明Sδ是δ-极限互模拟。 实际上，如果（W，{Vn：n∈D}）∈Sδ，则命题4.2中的条件对所有α∈Act成立。因此，我们认为，WJ<$δlimVJ（WJ <$δlimVJ）成立。根据nn∈Dnk∈BD}）∈ S δ（（W J，{V k：k ∈ B}）∈ S δ）. 通过δ-极限互模拟的定义，S δ是δ-极限二分法。所以，W边缘;n∈DQ根据拓扑学理论，极限是唯一的。对于δ-互模拟极限，我们还需要证明它是唯一的。下面的命题告诉我们，如果W和U是{Vn：n∈D}的极限，则W和U是δ-互模拟。命题4.3设Q =（A，θ）是一个QTS，δ∈L. W，U∈ P和{V n：n∈D} ∈δ δ δPN.如果W∈ lim V n，U∈ lim V n，则W∈ U。n∈D n ∈DδY. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）738312δδαPn∈DδδαδδδδδδδδδδδBBδδδ→δδ→证据 自WlimVn，U∈δlimVn，我们可以发现S1和S2是δ-极限双辛，n∈D n∈D假设使得（W，{Vn：n ∈ D}）∈ S1，（U，{Vn：n ∈ D}）∈ S2. 接下来需要构造一个δ-极限互模拟Sδ<$P × P，使得（W，U）∈Sδ.由命题3.4可知，sub（S）和sub（S）是δ-极限互模拟.因此，我们认为，δ δ令Sδ=sub（S1）<$sub（S2），其中关系的合成定义如下：sub（S1）<$sub（S2）={（W，U）：存在{Vn：n∈D}∈Psuch（W，{Vn：n∈D}）∈ sub（S1）和（U，{Vn：n ∈ D}）∈ sub（S2）}，对任意S，SJ<$P× PN.现在假设（W，{Vn：n∈D}）∈sub（S1），（V，{Vn：n∈D}）∈sub（S2）.由于S1和S2是δ-极限互模拟，我们知道sub（S1）和sub（S2）也是δ δ δ δ推论3.5中的δ-极限二等分。如果W→αWJ，则存在{VJ：n∈D}∈nβnP ，β对于n∈D和n ∈ Act ∈D使得V VJ和θ（α，β）≥δ，对于每个N n0J Jn→nnn≥ n0，且（W，{Vn：n ∈ D}）∈ sub（S1）. 因为D[n0）是D的一个闭子集，并且VβNVJ（n≥n），（V，{V：n∈D}）∈sub（S2）暗示存在VJ∈ P，n→n0nδ γγ∈Act和D[n0）的一个有限子集B满足V→VJ，（VJ，{Vb：b∈B}）∈sub（S2）当b ∈ B时，θ（γ，β b）≥ δ. 因此，B是D [n0）的一个有限子集，导致B是D的一个 子网，{Vb：b ∈ B}是{VnJ：n ∈ D}的一个子网。此 外 ，委员会认为，（WJ，{Vbj：b∈B}）∈sub（S1）. 所以，（WJ，VJ）∈sub（S1）<$sub（S2）. 由于θ是L值的，等式关系，θ（α，βn）≥δ（n≥n0），θ（γ，βn）≥δ（n∈B<$D[n0））. 所以，当n∈B时，θ（α，γ）≥δ.因此，如果V→VJ，则存在WJ∈ P，β∈Act，使得（WJ，VJ）∈sub（S1）<$sub（S2）且WβWJ和θ（α，β）≥ δ。Q命题4.4指出，如果两个规格W和V非常相似，并且规格W是某些实现的极限，则V也是这些实现的极限。命题4.4设Q=（A，θ）是一个QTS，δ∈L，W，V∈ P，{Vn：n∈D} ∈δ δ δN. 如果WV，且Wlim V n，则Vn∈D边缘;n∈D是的。自1988年以来，limVn，存在Sδ<$P ×PN是δ-极限互模拟，（W，{Vn：n ∈ D}）∈ S δ. 我们可以构建以下集合。SJ={（V，{Vn：n∈D}）：存在W∈Psuch使得W<$δV且（W，{Vn：n∈D}）∈S δ}.我们只需要说明SδJ是一个δ-极限的二分模拟。事实上，令（V，{Vn：n∈D}）∈SJ，则有W∈P，使得W∈δV且（W，{Vn：n∈D}）∈Sδ. 如果V→VJ，β则W<$V导致存在WJ∈ P和β∈Act使得WW WJ，并且δ→θ（α，β）≥ δ，且W J<$V J。 由于（W，{Vn：n ∈ D}）∈ S δ，存在γ n∈ Act，γnn∈D，{VJ：n∈D} ∈ P ，n ∈D使得VVJ，θ（β，γ）≥δ，对于每个nN0J Jnnn J J Jn≥n0且（W，{Vn：n∈D}）∈S δ. 因此我们得到（V，{Vn：n∈D}）∈Sδ。由于L是完备格，θ是L-值等式关系，δ∼84Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73满意，即，δ≤θ（α，β）<$θ（β，γn）≤θ（α，γn），即，对任意n≥n0，θ（α，γn）≥δ.Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7385δ→δδnδn∼{Wn：n∈D}∈PN和{Vn：n∈D}∈PN。若对任意n≥n0，Vn∈Wn，nNn→1nnn∈D[n0）n221n→nn0nNnn →nβbδn另一方面，如果B是D和V VJ的一个闭子集，对于每个b∈B，b→则（W，{Vn：n∈D}）∈Sδ蕴含存在β∈Act，WBP，一个常数。βB的子集H，使得W→当k∈H时，WJ，θ（α k，β）≥ δ，且（Wj，{Vk：k∈H}）∈γSδ。 由于W <$V，存在γ ∈ Act和VJ∈ P使得VVj，θ（β，γ）≥δ，和WJ<$VJ。 因此，由于L是完备格，θ是L值等式，关系，传递性可导致θ（αk，γ）≥θ（αk，β）<$θ（β，γ）≥δ，k∈H。 从而得到（VJ，{Vkj：k∈H}）∈SδJ. 因此，SδJ是δ-极限bisimulation和（V，{Vn：n∈D}）∈SδJ，即，V边缘;Qn∈D下面的命题4.5指出，如果两个团队的实现从某些修改中非常相似，并且一个团队的实现是基于规范W获得的，那么另一个团队的实现也是基于相同的规范。命题4.5设Q=（A，θ）是一个QTS，δn∈L，其中 n∈D， W∈ P，δnδnn≥ n，且 Wn∈D[n0）利姆Wδn，则Wn∈D[n0）利姆湾0∼n∈D[n0）nn∈Dδnn∈Dn证据 由于W当Wn为零时，存在Sδn P × PN，使得n∈D（W，{Wn：n∈D}）∈Sn∈D[n0）n∈D[n0）δn。 我们构造集合SJn∈D[n0）δn ={（W，{V，n：n∈D}）：存在{Wn：n∈D} ∈PN使得（W，{Wn：n∈D}）∈Sn∈D[n0）δn，且对某些n0∈D，Wn <$Vn（n≥ n0）.我们只需要让SJn∈D[n0）δn 是一n∈D[n0）δ n-极限互模拟。 事实上设（W，{Vn：n∈D}）∈SJn∈D[n0）δn。 则我们有（W，{W n：n ∈ D}）∈Sδnn∈D[n0）并且存在n0∈D，使得Wnδ<$nVn（n≥n0）. 如果W→WJ，则（W，{Wn：n∈D}）∈Sn∈D[n0） δn 设n∈D，存在βn∈Act，{WJ：n∈D} ∈ P和n∈D使得Wβn WJ，θ（α，β）≥δ，n≥n0，且（WJ，{WnJ：n∈D}）∈Sn∈D[n0）δn。因为D是有向集，所以存在n∈D使得n≥n和n≥n。因此，我们可以得到WβnWJ和W1995年γn对于每个n≥n。所以，存在VJ∈ P和γ∈Act使得VVJ，θ（γn，βn）≥δn，且当eachn≥n2 时，WnjVnj。因此，对于{Vn：n∈D}∈PN，Jδα02n86Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73J存在n2∈D，{VnJ ：n∈D} ∈ PN和γn∈Act使得Vnγn→Vn，θ（α，βn）≥n∈D[n0）δn，其中n≥n2≥n1，且θ（βn，γn）≥δn≥n∈D[n0）δn，每个n≥n2。此外，由于θ是L值等式关系，我们有，Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7387αmJ∼∼∼\nMNMm→MMM0个）θ（α，γn）≥θ（α，βn）<$θ（βn，γn）≥n∈D[n0）δ n对每一个n≥ n2。相反，如果C是D的一个有限子集，且对每个chm∈C，Vmα→MVJ，则M由于C [n0）<$C是一个有限子集，对每个m ∈ C [n0），我们可以得到Vm →Vm。当n ≥ n0时，Wnδ<$nVn导致Wmδ<$mVm，m∈C[n0）. 因此βm存在WJ∈ P，β∈Act使得WWJ，θ（α，β）≥δ，m∈C[n.由于（W，{Wn：n∈D}）∈Sn∈D[n0）δn和C[n0]的关系，其中D是一个闭子集，存在WJ∈ P，γ∈Act，C[n0]的一个闭子集Bγ满足W→WJ，θ（βb，γ）≥n∈D[n0）δn，b∈B，且（WJ，{WbJ：b∈B}）∈Sn∈D[n0）δn。 因此，我们可以得到一个C的有限子集B，使得（WJ，{WbJ：b∈B}）∈SJn∈D[n0）δn。 因为θ是一个L-值等式关系，对b∈B，θ（βb，γ）≥n∈D[n0）δn和θ（αm，βm）≥δ，当m∈C[n0）.因此，θ（αb，βb）≥δ≥n∈D[n0）δ n当b∈B时。的传递性，L-值等式关系，我们有θ（αn，γ）≥n∈D[n0）δ n，其中n∈B。因此，我们认为，SJn∈D[n0）δn是an∈D[n0）δ n-极限互模拟。Q5δ- 互模拟极限的替代律系统的设计需要多个不同的模块。为了实现灵活的分层开发和模块化设计方法，在这一节中，我们将主要讨论δ-互模拟极限在各种组合子下的替代性规律。首先，我们将介绍对下面的理论有用的定义。定义5.1[δ-round]设L是完备格，θ是X上的L-值等价关系。δ∈L，Y<$X，x∈Y，θ（x，y）≥δ蕴涵y∈Y，则称Y是δ-round的.定义5.2 [非收缩]设L是完备格a，θ是X上的L值等式关系。f是从X到自身的映射。如果对任意x，y∈X，θ（f（x），f（y））≥ θ（x，y），则称f是非收缩的。定理5.3设Q =（A，θ）是一个QTS，δ n∈ L，θ是Act上的L值等式关系.(i) 如果W<δlimVn，则α.Wδn∈Dlimα.Vn;n∈D(ii) 如果W<δlimVn，则W+Rδn∈Dintn（n）;n∈D(iii) 如果W<δ(iv) 如果W<δlimVn，theNW[f]δn∈DlimVn，则W Lδn∈D88Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73\nlimVn[f]，当f是非线性时。n∈DlimVnLwhenActL<$isδ-roundn∈DY. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7389ααα→δ∈ P∈nn→nn→nnN0→Mβn∼证据首 先 ，我们证明定理5.3 中的第一项。 如果α.W → W，则根据定义2.2中的过渡规则Vn，对n yn ∈ D，θ（α，α）=1≥δ∈L. Furanh，sinceW.(i) 第4.2章坚持limVn，条件n∈D另一方面，如果C∈D是一个闭子集，且α.Vm→Vm，m∈C，则我们有W∈ P，β=α∈Act和C的一个有限子集B=C，那么α.W→ W和θ（α，α）= 1≥δ，对任意m∈C和W∈边缘; 所以n∈D命题4.2中的条件（ii）成立。第4.2章可以保证α.Wδlimα.Vn保持n∈D(ii) 我们给出了定理5.3中的第二项. IfW+R→αWJ，那么有两种情况W→αWJ或R→αWJ。情形1：如果W→WJ，则WlimVn导致存在{VJ：n∈D} ∈ PN，β对任意n∈D和n∈Actn∈D∈D使得Vβn VJn和θ（α，β）≥δ，n≥n0且WJ<$δlimVJ. 根据传递规则J和J在定义2.2中，我们有NJn∈D即R+V VJ。 因此，存在{VJ：n∈D} ∈ P和n∈D，使得βnR+V VJ，θ（α，β）≥δ，对于每个n≥n和WJ<$δlimVJ。你知道吗？n→nn0nn∈DW+Rδlim（Vn+R）.n∈D情形2：若R→αWJ. 根据定义2.2中的过渡规则JSumJ，JR+Vn→αWJ，其中n∈D. 对于每个n ∈ D，LetVj =WJ。然后我们可以找到JnαJ一个过程网{Vn：n∈D} ∈PN且n0=n，对某个n∈D，R+Vn→Vn，θ（α，α）=1≥δ且Wj<$δlimVj. nn∈D相反，如果CD是一个有限子集，R+Vβm VJ对于每个m∈C.然后通过定义2.2中的转换规则βVJ为J或RβmVj对每个m∈ C。m→m情况1：如果VmMβm→Vm对于每个m∈C.由于C_∞D是一个有限子集，WlimVn，存在C，WJ和α Act的有限子网B，使得n∈D当m ∈ B时，W→αWJ，θ（α，βm）≥δ，且Wj<$δlimVj. 转换规则Mm∈B在定义2.2中可以告诉我们W+R→αWJ。所以我们知道W+R<$δlim（R+Vn）.n∈D情形2，若RβMVJ，其中eachm∈C，则R∈δlimR和C∈D是一个常数→mn∈D子集B∈C，α∈Act，WJ∈P，满足R→αWJ，αδδ0nMJ90Y. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）73θ（α，βm）≥δ，其中m∈B且WJ <$δlimVJ. 在此条件下，W+R→αWJ. 你好，我们好可以得到W+R<$δMn∈Blim（R+Vn）n∈D(iii) 我们证明了定理5.3中的第三项。 自WlimVn，存在n∈DδY. Ma，H.Pan/Electronic Notes in Theoretical Computer Science 333（2017）7391αα¯→γn →nn0nδ0n→n0n→nn0nnδ→MMMMMMγm→M→βnSδ是一个δ-互模拟使得（W，{Vn：n∈D}）∈Sδ.接下来，我们构建一个δ-二进制SδJ<$P×P。我们需要提供（W，{Vn：n∈D}）∈SδJ。α设SδJ={（W[f]，{Vn[f] ：n∈D}） ：（W，{Vn：n∈D}）∈Sδ}. IfW[f]→WJ，β那么我们有WWJ J，α=f（β）和WJ=WJ J[f]。由于（W，{V：n∈→JJnD}）∈S δ，存在{Vn ：n∈D} ∈ PN且γn∈Act，对任意n∈D，γn对任意n ≥ n，VVjj，θ（β，γ）≥δ，且（WJJ，{VJJ：n∈D}）∈S.通过定义2.2中的转移规则JRefJ，我们得到V[f]f（γn）VJ[f]f或nnJJJeachn≥n0. 由此，我们可以找到一个过程网{Vn=Vn[f] ：n∈D}∈PNf（γn）且n∈D，使得对任意n≥n，V[f]VJ。如果f是不可伸缩的，对任意n ≥ n0，θ（α，f（γ n））= θ（f（β），f（γ n））≥θ（β，γ n）≥δ.同时，根据SδJ的定义，我们知道（WJJ [f]，{Vnj[f]：n∈D}）∈SδJ.另一方面，如果CD是一个闭子集，则V[f]βmVJJ，thenVγm VJJJJJm→mm→m，βm=f（γm），Vm=Vm[f]。如果nce（W，{Vm：m∈D}）∈Sδ，存在WJJ∈ P，C的一个有限子集B和α∈Act满足W→WJJ，且θ（α，γm）≥δ，其中m∈B且（WJJ，{Vmj：m∈B}）∈Sδ. 通过转移规则JRelJ在定义2.2中，W[f]f（α）WJ[f]。 因此，设WJ=WJ J[f]。则W[f]f（α）WJ且（WJ，{VmJ→ →：m∈B}）J ≥当m∈B时，θ（α，γm）≥δ.∈Sδ。 f是非收缩的，可以保证θ（f（α）
我的内容管理
展开
