没有合适的资源?快使用搜索试试~ 我知道了~
结构运算语义中的零元素和单位元素的规则集
理论计算机科学电子笔记265(2010)145-160www.elsevier.com/locate/entcs关于零元素和单位元素的规则集Luca Aceto1 Matteo Cimini1 Anna Ingolfsdottir1雷克雅未克大学Menntavegur 1,IS 101雷克雅未克,冰岛穆罕默德·礼萨·穆萨维雷尼尔2埃因霍温理工P.O. Box 513,NL-5600 MB埃因霍温,荷兰摘要本文提出了一种结构运算语义的规则格式,保证某些常数作为一组二元运算符的左或右零元素。我们的设计方法也适用于重新制定一个较早的规则格式的一些作者开发的单位元素。左和右零,以及单位,从文献中的元素的例子被证明是可检查的使用所提供的格式。关键词:结构操作语义,GSOS格式,互模拟等价,零元,单位元1介绍在 的 最后 三 几十年来, 结构业务语义(SOS)、你看, 例如,在一个实施例中,[4,17,19,20],已被证明是一种强大的方式来指定语义编程和特定语言。在这种语义方法中,语言可以在状态和转换方面给出明确的行为,其中转换的集合通过一组语法驱动的推理规则来指定。基于这种语义的状态转换,我们经常想证明一般的代数法律的语言,其中描述的各种运营商的语义属性,他们涉及模的概念行为等价或前序的利益。例如,读者可能会想到过程领域,[1] Aceto、Cimini和Ingolfsdottir的工作得到了“操作语义学新定义”项目的部分支持。080039021)和“元理论的代数过程理论”(nr。100014021)冰岛研究基金。2电子邮件:m.a. tue.nl1571-0661 © 2010 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2010.08.009146L. Aceto等人理论计算机科学电子笔记265(2010)145代数,其中重要的是检查某些运算符是否是,比方说,关于双相似性的交换和结合本文旨在为正在进行的研究做出贡献,其目标是通过设计来确保代数性质的有效性,使用所谓的SOS规则[5]。这个研究领域的结果大致表明,如果一种语言的操作语义(部分)的规范具有某种形式,那么某些语义属性就保证成立。SOS的文献为算子的基本代数性质提供了规则格式,例如交换性[16],结合性[12]和幂等性[1]。这种方法的主要优点是能够通过可以机械化的语法检查来验证所需的属性。 此外,委员会认为,开发用于建立语义属性的规则格式是令人感兴趣的,因为如此获得的结果适用于广泛的语言类别最近,一些作者在[6]中提供了一种规则格式,保证了另一个以前没有提到的基本代数性质:算子的左和右单位元的存在性。在本文中,我们遵循[6]中提出的工作,我们开发了一个规则格式,而不是保证某些常数作为一组二元运算符的左或右零元素。也就是说,函数f有一个左(分别,右)零元素c,模一些行为等价的概念,每当方程f(c,x)=c(分别,f(x,c)=c)成立。满足上述方程的常数c也被称为对算子f是吸收的。在进程代数领域中左零元素的一个经典例子是BPA [9]中的常数δ,用于死锁,它满足以下定律:δ·x=δ和δx=δ,其中在本文中,我们在Bloom,Istrail和Meyer [11]的GSOS语言中制定了我们的零元素格式。特别是,我们受益于一些作者在[2]中开发的转换公式的逻辑,该公式是为推理GSOS规则的前提的可满足性而定制的。(The论文的完整版本[3]也给出了适用于左零元素和右零元素的语法规则格式,SOS规则比GSOS规则更普遍论文的最后一部分是致力于应用的设计思想, 基于GSOS的左零元素和右零元素格式,[6]中的左和右单位元素。由此产生的格式在功能上与原始格式无法比拟,但它的表现力足以检查[6]中讨论的所有示例在工具集中实现规则格式的机械化是SOS规则格式研究的一个长期目标。我们相信,我们在本文中提出的基于GSOS的规则格式是机械化的强有力的候选人,就零和单位元素而言。L. Aceto等人理论计算机科学电子笔记265(2010)145147⊆→文件路线图第2节重复了SOS理论和从[2]的初始转换的逻辑。 第3节提供了左零元素和右零元素的格式,第4节展示了文献中左零元素和右零元素的几个例子如何适合该格式。 在第5节中,我们提供了规则格式对于单元元素,采用第3节中的思想。我们在第6节总结了论文的主要贡献,并提到了可能在论文完整版中找到的进一步结果[3]。2预赛在本节中,我们回顾SOS理论中的一些标准定义。我们建议读者,例如,[4][17]更多信息。2.1变迁系统的规范和双相似性定义2.1 [签名,术语和替换]我们让V表示无穷多个变量,并使用x,xJ,x i,y,yJ,y i,. 在V的元素范围内。签名符号是一组函数符号,每个符号都有固定的元数。我们称这些符号为运算符,通常用f,g,.表示。. . .元数为零的运算符称为常数。我们定义T(n)为满足以下约束的最小集合。• 变量x∈V是一个项。• 如果f ∈ N有元n和t1,…, t n是项,则f(t1,..., n)是一个术语。我们使用s,t,可能带下标和/或上标,来范围术语。如果t1和t2在语法上相等,我们写t1<$t2函数vars:T(V)→ 2V给出出现在一项中的变量的集合。集合C(k)T(k)是闭项的集合,即,不包含变量的术语。我们用p,q,PJ,pi,。。在封闭的条件下变化。 置换σ是V型函数T(λ)。 我们扩展同态地对项进行替换的域,并将对项t应用替换σ的结果写为σ(t)。如果一个置换的值域在C(n)中,我们说它是一个闭置换。定义2.2[过渡系统规范]过渡系统规范(TSS)是一个三元组(L,D),其中• 这是一个签名。• L是一组由a,b,l排列的标签(或动作)。 若l∈L,且t,tJ∈ T(τ)我们认为t→LTJ是正变换公式,t~l是负变换公式公式一个转移公式(或仅仅是公式),通常用φ或φ表示,是一个负转移公式或正转移公式。• D是一组演绎规则,即,形式为(Φ,φ)的元组,其中Φ是一组公式,φ是一个正公式。我们把Φ中包含的公式称为规则的前提,把φ称为结论。148L. Aceto等人理论计算机科学电子笔记265(2010)145φ→LL01101我们写vars(r)来表示演绎规则r中出现的变量集合。我们说一个公式或一个演绎规则是封闭的,如果它的所有项都是封闭的。替换也以自然的方式扩展到公式和公式集对于规则r和替换σ,规则σ(r)称为R. 一组正的闭公式称为过渡关系。我们经常把mulat→ltJ的位置转换称为tbeing的转换它是源,l是标签,tJ是目标。 演绎规则(Φ,φ)通常写为Φ。 公理是具有空前提集合的演绎规则。当最外面的函数符号出现在它的源中时,我们称演绎规则f -defining结论是f。在本文中,对于每个常数c,我们假设每个c-定义演绎规则是形式为c→lp的公理,对于某个L项和D项p。这不是真正的限制,因为我们所知道的所有实际情况确实满足这个属性。对于GSOS语言[11],其定义如下,这将是我们在本研究剩余部分的重点,这一限制自动满足。定义2.3[GSOS规则]假设签名是一个签名。GSOS规则r对r的规则是以下形式的规则:l,x国际新闻报 y|1≤j≤m,∪l.x~bik|1≤k≤ni=1i→ijii=1if(x1, . ,xl)→ct我(一)其中所有变量都是不同的,m i,n i≥ 0,a ij,b ik和c是来自有限集合的动作,f是来自具有元数l的函数符号,t是T(t)中的项,使得vars(t)<${x1,...,x l}{y ij|1 ≤i≤l,1 ≤ j ≤ m i}。定义2.4GSOS语言是一个三元组G =(RNG,,RG),其中RNG是一个有限签名,是一个有限的动作标签集,RG是RNG上的GSOS规则集。与GSOS语言G相关联的转换关系G是由在闭的GSOS G-项上使用结构归纳的规则定义的。定义2.5(互模拟和双相似性[15,18])设G =(G,L,R G)是一个GSOS语言。一个关系R <$C(<$G)× C(<$G)是一个互模拟关系当且仅当R是对称的,并且对所有的p0,p1,pJ0∈ C(<$G)和l ∈ L,(p0Rp1p0→lGpJ)∈ C(G).(p1→GpJpJR pJ)。当存在互模拟关系R使得p0 Rp 1时,两项p0,p1∈C(G)是互模拟的,记为p0Participate-p1.将双相似性推广到开项,当σ(s)参与- - σ(t)时,要求s,t ∈ T(T)是双相似的.LL. Aceto等人理论计算机科学电子笔记265(2010)145149→L||⇒2.2初始过渡在本节中,为了完整起见,我们讨论了我们在定义基于GSOS的左零元素和右零元素的规则格式时使用的逻辑[2]中的一些作者最近引入了初始转换的逻辑,以便推理GSOS规则的前提的可有限个作用集L上的初始转移公式集由以下文法定义,其中a∈ L:F::=True|x→a|F F .|F ∧ F.像往常一样,我们把<$True写成False,把<$(<$F<$$>FJ)写成F <该逻辑的语义由满足关系给出,该满足关系相对于GSOS语言G=(ΣG,,RG)通过以下方式在F上的结构递归来定义,其中σ是闭合替换,G是可以使用RG中的规则证明的转换的集合:→ G,σ |= True 总是a a→ G,σ| = x →惠σ(x)→ Gp,对某些p→ G,σ| = € F优惠 → G,σ| = F→ G,σ| = F <$FJ惠→ G,σ| = F,且 → G,σ| = FJ.熟悉Hennessy-Milner逻辑[13]的读者会注意到,形式x→a的位置对应于Hennessy-Milner对于形式x-a-True的模的位置。在下面的内容中,我们考虑直到交换性和结合性的公式。我们使用该逻辑将GSOS规则的前提集合Φ转化为公式它描述了满足Φ的闭合替换的集合。转换程序hyps是借用[2]。从形式上讲,hyps()=Truehyps({x→ay}<$Φ)=(x→a)<$hyps(Φ\{x→ay})hyps({x~a}<$Φ)=<$(x→a)<$hyps(Φ\{x~a}).直觉上,如果Φ是规则的前提集合,那么hyps(Φ)是合取对应的初始转换公式。比如说,hyps({x→ay,z~b})=(x→a)(z→b).如果J是GSOS规则的有限集合,我们重载hyps并写:hyps(J)=hyps(Φr),r∈J其中Φr是规则r的前提集合。我们写=GF FJ i,每个满足F的替换也满足FJ。这种语义蕴涵前序是可判定的,如[2]所示定理2.6(蕴涵的判定性)设G是一个GSOS语言.然后,对于所有公式F和FJ,是否|= GF <$FJ成立。150L. Aceto等人理论计算机科学电子笔记265(2010)145|⇒∈›→LL›→›→›→(x→)[x<$→c]=否则为False事实上,当Φ是规则r的前提的集合时,检查是否|= G True ⇒ hyps (Φ) holds is equivalent to checking whether the rule r is alwaysfirable.相反,检查=Ghyps(Φ)False是否成立等价于检查规则r是否永远不会触发。这些考虑因素将在本文件的其余部分有所帮助。我们对左零元素和右零元素的规则格式的定义利用了逻辑,尤其是这两种蕴涵。此外,语义蕴涵是以一种简化的方式使用的,其中不需要检查所有闭合替换,而只需要检查那些将一个变量映射到所考虑的左或右零元素常数我们现在开始正式化这个概念。定义2.7设G =(G,,R G)是一个GSOS语言。对于每个公式F,常数c∈ G和变量x,我们通过F上的结构递归定义公式F [x c]如下:True[x›→c]=Truea.True 如果存在c-定义公理c→ap,(y→a)[x<$→c] =y→aifxy(<$F)[x<$→c]=<$(F[x<$→c])(F1<$F2)[x <$→c] =(F1[x<$→c])<$(F2[x<$→c]).F和F[x<$→c]之间的联系由以下引理提供。引理2.8设G=(G,,R,G)是一个GSOS语言. 设F是一个公式,c是一个常数,x是一个变量。然后,对于每一个封闭的置换σ,→ G,σ| = F [x <$→ c] i → G,σ [x <$→ c]|= F,其中σ[xc]表示将x映射到c的替换,并且在所有的 其他变量。作为上述引理的结果,检查F是否对将变量x映射到常数c的所有替换都成立,这相当于表明公式F[x c]被所有替换满足--即证明F[x c]是G上的重言式。3零元素在本节中,我们提供了一个规则格式,保证某些常数作为一组二元运算符的左零或右零元素。为此,我们采用了[6]中一些作者为左或右单位元素开发的技术的变体。与[6]一样,我们使用了术语之间的等价关系,称为零上下文等价,这是[6]中单位上下文等价的对应物。直觉,如果c是一个左零元素的运算符f和c也是一个L. Aceto等人理论计算机科学电子笔记265(2010)145151∈∈⊆×⊆×∈ →∈右零元素,则项f(c,t1)和g(t2,c)都是零上下文等价于c且零上下文相互等价。在以下零上下文等价的形式定义中,可以考虑(f,c)L表示“c作为算子f的左零元素”,类似地(f,c)R表示常数c是f的右零元素。定义3.1[零上下文等价项]给定集合L,RΣ对的平方L、R对于二元函数系统和常数,λ=0是最小等价关系满足以下约束条件,对于每个s∈ T(n):L、R(i)<$(f,c)∈L. c=0f(c,s),并且L、R(ii)<$(g,d)∈R. dθ=0g(s,d)。L、R我们知道,如果s∈ T = 0 t,则s,t∈T(T)是零上下文等价的.由于集合L和R总是从上下文中清楚,因此在L、R这篇文章写了=0代替=0。定理3.2(零上下文等价的判定性)设L,R≠ 0是二元函数符号和常数对的有限集合然后,对于所有项,L、Rt,u∈T(n),t ∈ 0u是否成立是可判定的。为了与[6]中的术语保持一致,在下面的定义中,我们讨论左对齐对和右对齐对。 我们格式的条件将不会试图通过语法手段来确保规则的可靠性/不可靠性,就像[6]中的单元元素的规则格式一样,但他们反而利用初始转换公式的逻辑来将少量的语义推理纳入规则格式。定义3.3[左对齐和右对齐对]设G是GSOS语言。 二元函数符号和常数对的集合L和R是满足以下约束的最大集合。1. 对于每个(f,c)∈L,以下条件成立。a. 对于一个ch公理mc→at,存在一个规则集J,其形式为Φf(x0,x1)→atJ使得i. |=G True ⇒hyps(J)[x0c], andii. 对于J中的每个规则,以下情况之一成立:A. 有一些变量yvar s(tJ)suchthatx0ayΦ和σ(TJ)<$=0t,其中σ是x0到c,y到t的置换映射,并且是所有其他变量的恒等式,或者B. σ(tJ)n=0t,w这里σ是x0到c的置换映射,d是所有其他变量的恒 等式 。152L. Aceto等人理论计算机科学电子笔记265(2010)145∈ →∈→b. 对于每个f-定义演绎规则,Φ一f(x0,x1)→tJ下列情况之一成立:i. 存在公理c→atsuch,A. 有一些变量yvar s(tJ)suchthatx0ayΦ和σ(TJ)<$=0t,其中σ是x0到c,y到t的置换映射,并且是所有其他变量的恒等式,或者B. σ(tJ)n=0t,w这里σ是x0到c的置换映射,d是所有其他变量的恒 等式 。ii. |= G hyps(Φ)[x0<$→ c]<$False.2.右对齐的算子对和常数符号的定义--即那些使得(f,c)∈R的算子对和常数符号的定义--是对称的,这里不再重复对于一个函数符号f和一个常数c,我们称(f,c)左对齐(分别为,右对齐),如果(f,c)∈L(分别,(f,c)∈R)。设G是一个包含至少一个常数的签名上的GSOS语言由于hyps(J)是一个析取公式,条件1.a.i.在上面的定义中,意味着集合J是非空的。另一方面,条件1.b.ii.说,所考虑的规则的前提不能被任何将变量x0映射到常数c的封闭替换所满足。在条件1.a. 和它的对称对应物,我们必须确定一组J,规则为了理解为什么,读者应该考虑下面的TSS,其中常数为0(没有规则)和RUNa,函数符号f定义如下RUNa→aRUNa(y)x→axJy→ayJf(x,y)→axJ(非xaxJy~a.f(x,y)→axJ规则(y)和(非在定义3.3中,这两个性质分别由条件1.a.i.保证。和1.a.ii.定理3.4设G是GSOS语言. 假设L和R是根据定义3.3左对齐和右对齐的函数符号的集合。对每个(f,c)∈L,f(c,x)参与c.对称地,对每个(f,c)∈R,f(x,c)参与c.下面的结果是定理2.6和3.2的一个推论。定理3.5对于GSOS语言,集合L和R可以有效地构造。我们通过讨论定义3.3中的一些约束来结束本节L. Aceto等人理论计算机科学电子笔记265(2010)145153联系我们→{}{|联系我们/∈{}{}→以证明他们不能轻易放松。在下面的内容中,我们重点讨论左对齐对必须满足的条件。首先,请注意,放松GSOS规则的x0x1约束将危及定理3.4。要看到这一点,考虑具有常量RUN a和二元运算符f的TSS,x0→ay0.f(x0,x0)→ay0不难检查L=(f,RUN a)和R=满足GSOS规则和定义3.3的所有其他约束。由于存在公理RUNaa RUNa约束1.b.i.A。在这种情况下得到满足。然 而 ,RUN a不是f的左零元素。例如,f(RUN a,f(RUN a,RUN a))a项没有转换,因此不能与RUN a双相似。下面的例子表明,放宽GSOS要求x1yij1il,1jm i也会使定理3.4无效。要看到这一点,考虑具有常量RUN a和二元运算符f的TSS,x0→ax1.f(x0,x1)→ax1同样,不难检查L=(f,RUN a)和R=满足GSOS规则和定义3.3的所有其他约束。然而,f(RUN a,f(RUN a,RUN a))a没有转换,因此不能与RUN a双相似。这意味着RUN a不是f的左零元素。要求1.a.i.发挥的作用和1.a.ii.为了确保模双相似性,对于每个p,f(c,p)a例3.6考虑TSS,其中0和ab为常数,还有一个二元运算符f有规则:x0~bx0→ay0x0~ax0by0.b→a0b→b0f(x0,x1)→ay0f(x0,x1)→by0不难看出,L=(f、a、&b)和R=满足所有约束条件 在定义3.3中,除了1.a.i.特别地,f -定义演绎规则的任何单例集J满足约束1.a.ii.A。(以及约束1.a.)。然而,f(a&b,0)a项不像a b那样包含跃迁&。因此,a&b不是f的左零元素。☒例3.7考虑TSS,其中包含常量RUNa、RUNb和c,以及二元运算符f,其规则为:154L. Aceto等人理论计算机科学电子笔记265(2010)145--B联系我们x1→ay1x1→by1aRUNac→aRUNbf(x0,x1)→aRUNaf(x0,x1)→aRUNb令L= (f、c) R是空的。 我们主张,定义除1.a.ii.外, 要看到这一点,请注意,首先,每个封闭的术语,在这种语言中,最初a是a标记或b标记的转换。因此,我们认为,公式x1→ax1→是重言式y。 它遵循条件1.a.i. 可以通过取J包含两个f-定义规则,满足两个c-定义公理。遵守条件1.a.ii.对于这个J失败,但是条件1.b.i.B.通过将第一个f-定义规则与c的第一个规则匹配,以及将第二个f-定义规则与c的第二个规则匹配,满足两个f-定义规则。然而,c不是f的左零元素。例如,f(c,RUN a)只有a将a标记的跃迁转换为RUN a,因此不能匹配跃迁c→aRUNb。☒例如,通过下面的示例4.3,约束1.b.i.增强了我们格式的通用性。事实上,如果我们删除约束1.b.i.和一个左对齐对(f,c)满足条件1.b.ii.,则f的任何规则都不适用于f(c,p)形式的闭项。因此,没有f(c,p)形式的项会导致跃迁。因为(f,c)满足条件1.a。在定义3.3中,c-定义公理的集合必须为空。因此,结果格式将无法处理左零元素,如RUNa,它是一个转换的一部分。文献中具有演绎公理的常数的例子是立即死锁[8],它在顺序组合、并行组合、左合并和通信合并中充当左零元素,在并行组合和通信合并中充当右零元素,以及[7]中的延迟死锁,它是 用于顺序合成的左零元素4示例在本节中,我们将展示文献中几个零元素的例子,它们确实符合第3节中描述的格式。例4.1[同步并行组合]考虑CSP [14]中的同步并行组合,它是在一组动作L上进行的,规则如下:x→axJy→ayJxLy→axJ ǁLy J(a ∈ L).我们知道无作用常数0,没有规则,是L的左零元素和右零元素。设L=R=(L,0). 由于常数0没有公理,条件1.a.是空虚的满足。为了看到这一点,也条件1.b。 如果满足,那么我们就应该注意到,唯 一 的一条 关 于 0的规则永远不会被 触发,因为0没有转换。L. Aceto等人理论计算机科学电子笔记265(2010)145155一{}ǁ联系我们ǁ→ǁ一的确,|= G(x → Hy →)[x <$→ 0]假成立和条件1.b.ii.得到满足。条款1.b的对称对应物。以类似的方式处理。众所周知的法律0LyParticipate从定理3.4可以看出。☒例4.2[左合并运算符]考虑[9]中的左合并运算符x→axJxy→axJy这里代表[9]中的合并运算符,它的SOS规格对于这个例子来说并不重要;参见下面的例4.3设L=(,0),R=。 我们主张L满足定义3.3中的约束。用例4.1中所用的同样的推理,很容易检验这个主张是否正确。这一次检查条件1就足够了。因为0只是x的左零元素。根据定理3.4,y - 0定律的有效性如下。注意,对(,0)不能被添加到R,因为条件1.b的对称版本。将被侵犯。事实上,0不是n的右零元素。☒例4.3[Merge operator]设L为动作的集合。考虑具有以下规则的经典合并运算符,其中a∈ L。x→axJxy→axJyy→ayJxy→axyJ设RUNL是由公理RUNL→aRUNL定义的常数,对每个作用a∈L. 我们主张,常数RUN L是一个左零元素和右零元素。这可以用定理3.4来检验。事实上,令L=R= {(R, RUNL)}。很容易看出条件1.a。在定义3.3中,对于RUNLaRUNL,通过采用具有动作a的左手定则的实例,满足。条件1.b.是针对通过约束1.b.i.A满足的左手演绎规则。 由于存在动作a的RUN L的公理。对于具有动作a的右手定则,满足条件1.b.i.B,因为σ(x<$yJ)<$RUNL<$σ(yJ)<$=0RUNL对于置换σ,σ(x)= RUN L,否则它作为单位函数,并且RUNL→aRUNL是常数RUNL的公理之一。☒例4.4[一个右选运算符]在这个例子中,我们将我们的格式应用于一个非标准运算符。为了简单起见,我们假设a是唯一的动作。考虑Milner的CCS [ 15 ]的选择运算符的变体调度器仅在另一个没有转换时才执行左侧变元。这种操作符的规则如下:156L. Aceto等人理论计算机科学电子笔记265(2010)145←↔⊆×→⊆×x→axJy~ax←+y→axJYAYJ.x←+y→ayJ设c是任何常数,其行为由非空的有限公理集合{c→api|i∈I},其中I是某个指数集。 与前面的例子一样推理,利用定理3.4,我们能够证明x+c-c定律的有效性。我们把细节留给读者。本例中研究的运算符具有从[10]中,使用首选操作符→+进行☒5从零到单位在本节中,我们按照定义3.3的行重新制定[6]的单位元素格式。为了清楚和完整起见,我们在这里重复[6]中的单位上下文等价定义5.1 [单位上下文等价性[6]]给定集合L,R 对的平方L、R对于二元函数系统和常数,λ=是最小等价关系满足以下约束条件,对于每个s∈ T(n):L、R(i) n(f,c)∈ L.S(ii) n(g,c)∈R. Sf=f(c,s),并且L、Rn=g(s,c).L、R我们说两个项s,t∈ T(n)是单位上下文等价的,如果st=t。由于集合L和R在正文中总是很清楚的,所以我们在适当的地方写为L、R的=。定理5.2(单位上下文等价的判定性)设L,RΣΣ是二元函数符号和常数对的有限集合然后,对于所有项,L、Rt,u∈ T(n),则t = u是否成立是可判定的.定义5.3[单位元素的左对齐和右对齐对]给定GSOS语言G,二元函数符号和常数对的集合L和R是满足以下约束的最大集合1. 对于每个(f,c)∈L,以下条件成立:a. 对于每个动作a∈ L,至少存在一个演绎规则,其形式如下:Φ1{x1→ay1}哪里i. |=Gx1→a、f(x0,x1)→atJxhyps(Φ)[x0<$→c],以及ii. 下列情况之一成立:L. Aceto等人理论计算机科学电子笔记265(2010)145157B→ǁ{}A. 对于b∈L和y∈vars(TJ),存在一个前提x0→by∈Φ,且公理c→btsuch使得σ(tJ)n=y1,其中σ是置换映射x0到c,y到t,并且是所有其他变量的恒等式,或者B. σ(tJ)n= y1,其中σ是x0到c的替换映射,是所有其他变量的恒等式y。b. 对于每个f-定义演绎规则,Φ一f(x0,x1)→tJ下列情况之一成立:i. x1→ay1∈Φ,对某个变量y1,A. 或者存在一个前提x0→by∈Φ,对于某个b∈L且为变量y∈vars(tJ),such,c有一个公理,其中labelb-say,c→bt-和σ(TJ)n=y1,其中σ是x0到c,y到t的置换映射,并且是所有其他变量上的恒等式B. 或σ(tJ)n=y1,其中σ是x0到c的置换映射,是所有其他变量的恒等式。ii. |=G hyps(Φ)[x0c] ⇒ False.2.右对齐的算子对和常数符号的定义--即那些使得(f,c)∈R的算子对和常数符号的定义--是对称的,这里不再重复对于一个函数符号f和一个常数c,我们称(f,c)左对齐(分别为,右对齐),如果(f,c)∈L(分别,(f,c)∈R)。下面的定理说明了上面定义的规则格式的正确性定理5.4设G是GSOS语言。 假设L和R是根据定义5.3左对齐和右对齐的函数符号的集合。对每个(f,c)∈L,f(c,x)参与x.对称地,对每个(f,c)∈R,f(x,c)参与x.注5.5c的约束条件t是唯一带有标签b的c-定义公理在条件1.b.i.A.定义5.3中的一个条件是定理5.4有效的必要条件。为了理解这一点,考虑例如,具有常数0,RUN a和c的标签集{ a }上的TSS,以及例4.1中定义的二元运算符L。常数c的规则是.c→ac c→a0注意,如果从条件1.b.i.A中去掉唯一性要求,则集合L= L,c)和R=将满足定义5.3中的条件。另一方面,c LRUN a与RUN a不是双相似的,因为cLRUNa→a0LRUNa~a,而RUNa只能永远执行操作a。因此c不是一个左单位元素。☒158L. Aceto等人理论计算机科学电子笔记265(2010)145--{}ǁǁ关于我们→下面的结果是定理2.6和5.2的一个推论。定理5.6对于GSOS语言,集合L和R可以有效地构造。上面提出的左和右单位元素的格式与[6]中提出的格式是不可比较的。实际上,后者允许使用复杂的术语作为结论的来源和前提,而这是GSOS格式所禁止的。另一方面,在条件1.a.在上面的例子中,前提集合Φ可以包含对自变量变量x1的几个测试,这是[6]中的纯语法格式所禁止的。下面将讨论一个具体的TSS利用此功能的示例,尽管无可否认的是,该示例并不明确例5.7考虑一个TSS,在标签a,b的集合上,具有常数RUN a和RUN b,以及一个二元函数符号f,由下面的规则定义。y→ayJy~by→byJy~af(x,y)→ayJf(x,y)→byJ常量RUN a和RUN b都是f的左单位元素。事实上,每个闭项都是f的左单位元。这是因为每个闭项都与常数RUN a和RUN b中的一个双相似。因此,每个进程要么最初能够执行a-转换,要么最初能够执行b-转换,但不能同时执行两者。不难检验集合L=(f,RUNa),(f,RUNb)和R=满足定义5.3中的条件。另一方面,[ 6 ]中的格式在这个基本场景中失败了,因为y在f的规则中被测试了两次。 ☒[6]中提到的文献中的所有例子都可以用定义5.3中给出的规则格式来处理。为了说明,我们仅限于讨论[6]中提到的一个例子例5.8 [同步并行合成]假设a是L中唯一的动作。 考虑例4.1中的常量RUN a和同步并行复合运算符L。 为了便于参考,我们回顾L由以下规则指定:x→axJy→ayJxLy→axJLyJ(a ∈ L).取L=R=(L,运行a)。这些集合L和R满足定义5.3中的约束。我们先来讨论一下集合L。1.a. 考虑一下规则a或b。由于(x→a)[x<$→RUNa]=True,a a|= Gy →(x →)[x →运行a]满足感是微不足道的。因此,条件1.a.i.得到满足。此外,注意,xa xJ是上述规则的前提既然我们可以选择公理RUNa→aRUNa,L. Aceto等人理论计算机科学电子笔记265(2010)145159ǁ ≡ǁ以及将x和 XJ映射到游程 a的代换σ,它是所有其他变量的恒等函数。 则σ(xJLyJ)RUNaLyj=yJ. 因此,条件1.a.i.A。得到满足。1.b. 通过上述推理,我们可以很容易地检验上述规则是否满足条件- 第1.b.i.A.定义5.3。类似的推理表明,(RNL,RUN a)也是右对齐的。☒6结论在本文中,我们提供了一个规则格式,确保某些常数在语言中作为左或右零元素的二元运算符集。 第3节中给出的左零元素和右零元素的格式遵循了一些作者在[6]中开发的技术,其中给出了左单位元素和右单位元素的格式,但实际细节相当不同。该格式使用了[2]中提出的初始转换逻辑,并且仅限于所谓的GSOS语言。因此,它不包括高级特征,例如在规则结论的来源中的复杂术语,就像[6]中的单位元素一样,但仍然能够检查相关情况。在零元素格式的设计之后,我们还为左和右单位元素提供了一个alter-native规则格式。尽管该格式与[6]中的格式不可比,但它仍然能够检查文献中的所有相关病例以及[6]中格式未解决的一些基本单元元素。我们相信,我们在本文中提出的格式GSOS语言是很好的候选人机械化的工具集检查代数法律的基础上规则格式。在本文的完整版本[3]中,我们还给出了零元素的格式, 不局限于GSOS语言,而是更紧密地遵循[6]的方法,并将其应用于文献中的各种例子。在本文中,我们没有包括任何关于在演绎规则中使用前提的材料。在[3]中,我们证明谓词可以很容易地处理。引用[1] 阿塞托湖,A. Birgisson,A.因戈尔夫斯多蒂尔湾R. Mousavi和M. A. Reniers,Rule formats fordeterminism and idemonism , in : F. Arbab 和 M. Sirjani , editors , Fundamentals ofSoftwareEngineering , Third IPM International Conference , FSEN 2009 , Kish Island , Iran ,April 15-17,2009,Revised Selected Papers,Lecture Notes in Computer Science5961(2010),pp. 146-161[2] 阿塞托湖,M. Cimini和A. Ingolfsdottir,一种基于双模拟的方法,用于证明GSOS语言中方程的有效性,在:Proceedings of Structural Operational Semantics 2009,2009年8月日,博洛尼亚(意大利),Electronic Proceedings in Theoretical Computer Science18,2010,pp. 1比16[3] 阿塞托湖,M. Cimini,A.因戈尔夫斯多蒂尔湾Mousavi和M. A. Reniers,关于零和单位元素,技术报告CSR 10/03,TU/e(2010)。[4] 阿塞托湖,W. Fokkink和C. Verhoef,Structural operational semantics,in:Handbook of ProcessAlgebra(1999),pp. 197-292.[5] 阿塞托湖,A.因戈尔夫斯多蒂尔湾Mousavi和M. A. Reniers,代数属性免费!,EATCS99(2009)公报81-104160L. Aceto等人理论计算机科学电子笔记265(2010)145[6] 阿塞托湖,A.因戈尔夫斯多蒂尔湾Mousavi和M. A. Reniers,Rule formats for unit elements,in:J.vanLee uwen,A. Mus choll,D. Peleg,J. 波孔尼和B。 Rum pe,编辑,SOFSEM2010,第36 届计 算 机 科 学 理论与实践会议, Spin dleruvM l′yn , Cz echRepublic , 2010 年 1 月23 日 至 29 日 。Proceedings,Lecture Notes in Computer Science 5901(2010),pp. 141-152.[7] Baeten,J.,T. Basten和M. Reniers,[8] Baeten,J.和C.陈文,[9] Bergstra,J.和j.W. 陈文辉,“进程代数中的不动点语义”,北京:清华大学出版社,1982。[10] Bergstra,J.A. 和C.A. 米德尔堡,优先选择和协调条件,J。Log. 代数程序. 70(2007),pp. 172-200[11] Bloom,B.,S. Istrail和A. R. Meyer,互模拟232-268。[12] Cranen,S.,M. Mousavi和M. A. Reniers,A rule format for associativity,in:F. van Breugel和M.19th International Conference on Concurrency Theory(CONCUR447-461[13] Hennessy,M.和R.Milner,非确定性和并发性的代数定律,J。ACM32(1985),pp.137-161。[14] 霍尔角A. R.,通信顺序进程,Commun。ACM21(1978),pp.666-677。[15] 米尔纳河, 上鞍河,新泽西州,美国,1989。[16] Mousavi,M.,M. Reniers和J.F. Groote,A syntax commutativity format for SOS,InformationProcessing Letters93(2005). 217-223[17] Mousavi,M. R.,M. A. Reniers和J.F. 《SOS格式与元理论:20年后》(SOS formats and meta-theory:20 years after)Comput. Sci. 373(2007),pp. 238-272。[18] 帕克,D.,Concurrency and automata on infinite sequences,in:Proceedings of the 5th GI-Conference on Theoretical Computer Science(1981),pp.167-183。[19] Plotkin,G.D、A Structural Approach to Operationa
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功