没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记157(2006)3-21www.elsevier.com/locate/entcs基于半环的移动系统本杰明·阿齐兹伦敦帝国理工学院计算机系180 Queens Gate英国伦敦SW7 2AZ摘要在本文中,我们提出了半π,π演算的一个扩展,允许过程查询不同动作的量化值,并根据这些值决定一个动作是否可行。我们的量的度量是基于半环的一般概念。此外,我们开发了一个语法导向的静态分析的新语言,它捕获的属性的名称替换和半环值检索。这些属性使我们能够解决定量约束控制同步的分析系统。我们提供了一个简单的自适应路由算法的通信成本分析的例子。保留字:静态分析,数量资源,半环,移动系统1介绍在本文中,我们提出了一个语法导向的静态分析的π演算[14]的扩展与半环值检索能力和半环约束。这种新语言被称为semi-π,允许进程在给定某些信息的情况下查询通信动作的基于该成本,流程可以通过使用半环约束来决定它接下来应该执行的行为例如,在这个过程中,1电子邮件:baziz@doc.ic.ac.uk1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.01.0204B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3令ω1=S值(x<$y<$,t),令ω2=S值(u <$y<$,t),[ω1ω2]xy|[ω2ω1]uωy然后,在使用中的let=S值()检索时间t时的动作成本xy和uy之后,并将结果放置在ω1,ω2中,我们使用某种排序关系比较两个成本,并选择任一输出。然后,静态分析捕获了所分析系统的两个属性:第一个是名称替换,这是同步操作的结果,第二个是给定特定上下文信息的操作成本的实例化使用这些属性,可以根据导致这些替换的操作成本来量化名称这些属性在自适应网络路由的分析中有着有趣的应用,其中路由器根据其邻居的不同路径的成本来计算每个数据包的输出端口我们的成本度量是基于半环的概念。 一个半环是元组,(A,+,×,1, 0),使得A是一个集合,0, 1∈ A。此外,+是加法运算,它是交换和结合的,以0作为其单位元素,而×是乘法运算,它是结合的,以1作为其单位元素,0作为其吸收元素。一个半环具有×分布在+上的性质此外,在[7]之后,可以定义基于+的排序关系:ssJ优惠 s+sJ=s有时我们写s>sj来表示ssJ和s sJ。这一措施代价是普遍的:文献中存在许多(A,+,×,1, 0)布尔的、概率的、模糊的、集合论的、加权的等等。论文的其余部分组织如下。在第2节中,我们讨论了一些相关的工作在移动系统的定量分析领域。在第3节中,我们介绍了半π语言的语法。在第4节中,我们定义了一个域理论模型作为半π的标准语义的基础。在第5节中,我们扩展了这个语义来捕获半环变量的名称在第六节中,我们对非标准语义进行抽象,以获得可计算的静态分析.在第7节中,我们演示了抽象语义的结果如何产生一个约束满足问题的解决方案,该问题涉及名称替换和动作成本之间的关系在第8节中,我们将分析应用于自适应路由器的一个简单示例。最后,在第9节中,我们总结了本文并讨论了未来的工作。B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)352相关工作本文中提出的工作是以前分析的延续[2,3,5,6],这些分析旨在基于移动和密码/PKI系统中的名称替换属性来检测安全属性,这些系统以π演算的不同版本(例如,[1]和Spiky [12])。目前工作的主要新颖之处在于,分析涉及定量属性(例如,名称替换的成本)而不是定性属性(例如安全属性)。在移动系统的定量分析领域的其他工作包括[8,9,13,17],在过程代数模型的定量分析领域,使用不同的方法进行了研究大多数这样的工作与我们的方法不同,因为一个过程对它的未来执行没有还有其他的定量分析[15,16],但这些分析通常是为更简单的、类似KLAIM的、没有名字传递的语言设计的。3半πsemi-π语言的语法定义见图1。 在这种语法中,名称构成无限集合,a,b,c,n,m,x,y,z. ∈ N。过程P,Q,R∈ P定义如下。一个受保护的进程,π.P,一旦它触发π,就像P一样继续,其中π是输入x(y)或输出x(y)。在x(y)的情况下,通过x接收的消息将替换P中的y。平行组合,P|Q通过交错P和Q来运行它们。限制(νn)P在P的作用域中产生一个新的名称n。复制,!根据上下文的需要,生成尽可能多的P副本。如果x与y相同,则匹配[x = y] P作为P进行,否则itblocks。类似地,半环约束[e1e2]P是P,如果e1e2,否则,它阻塞。 表达式e1,e2使用半环定义变量,ω∈Ω,元素s∈ A,加法算子的应用, e1+e2,乘法算子的应用,e1×e2。空进程0是一个无法进一步进化的进程我们通常省略尾随的空残基。最后,设ω=Svalue(π,n)inP,在给定某个名称n的情况下,检索动作π的半环值,并在P.直觉上,n充当可能需要的上下文数据,以便给出关于动作π的更具体的信息(例如,动作的时间、动作的相对位置、执行动作的用户的姓名等)。基于这个过程的定义,我们将系统E,F∈ E定义为对(θ,P),其中θ(π,n)=sπ,n∈ A是将每个通信动作π及其上下文数据n∈ N映射到某个对应6B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3P,Q,R::=过程π.P防护装置P|Q成分(νn)P限制!P复制[x=y]P匹配[e1e2]P半环约束0空设ω=S值(π,n)在P半环值检索中π::=守卫X射线衍射仪输出x(y)输入e::=表达式ω半环变量s半环元e1+e2加法运算e1×e2乘法运算E,F::=系统(θ,P)状态过程对Fig. 1. 半π语言的语法半环值,sπ,n∈ A.值sπ,n,在e中代表根据n给出的信息对作用π的量化。α-转换的标准概念以及一个过程P的自由名fn(P)和束缚名bn(P)都像通常那样定义,其中y在(νy)P和x(y).P中束缚于P。一个名字是自由的,如果它没有绑定。进一步,我们把bsemiv(P)称为P的有界半环变量集,即P过程中令ω=S值(π,n)中的ω,而把fsemiv(P)称为自由半环变量集,即出现在表达式中但不出现在bsemiv(P)中的变量.我们通常写semiv(P)=fsemiv(P)<$bsemiv(P)。从现在开始,我们只处理具有正常过程的系统。定义3.1过程P被称为正常的,如果下列条件成立:• 在P中没有出现同态约束名或同态半环变量。B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)37• bn(P)|fn(P)={}.• fsemiv(P)={}(无开放表达式)。4一个领域理论模型semi-π的标准语义定义在[4,5,18]的域理论风格中。假设Pi是过程的语义域,N是名称的前域,K是任何(前)域之下的集合,那么P i和N的具体元素可以如图2所示定义。N的元素:x∈ Nx∈ K(N)Pi的元素:{|⊥|} ∈ K(Pi)n ∈ K(Pin)p,q∈ K( Pi∈ K)⇒pq∈ K( Pi∈)x∈ K( N),p∈ K( Pi∈ N)⇒new(x,p)∈K(Pi∈)p∈ K( Pi∈ K)⇒{|τ(p)|} ∈ K(Pi)x,y∈ K( N),p∈ K( Pi∈ N)⇒{|in(x,λy.p)|} ∈ K(Pi)x,y∈ K( N),p∈ K( Pi∈ N)⇒{|out(x,y,p)|} ∈ K(Pi)x,y∈ K( N),p∈ K( Pi∈ N)⇒{|out(x,λy.p)|} ∈ K(Pi)图二. P i和N.N的定义是平凡的:N是一个可解的前域2。因此,它另一方面,Pi被定义为语义元素的多重集合,其中{|⊥|}是底部元素,表示未定义的进程和空的多集表示已终止或死锁的进程3。其他元素的定义如下:pq是两个元素p,q的标准多集并。 singleton map,||},获取表示输入、输出和静默操作的元组,并为每个元组创建一个单例多重集。这些元组是in(x,λy.p)(输入动作),out(x,y,p)(自由输出动作),out(x,λy.p)(绑定输出动作)和tau(p)(静默动作)。在这些元组中,x是通信通道,y是消息或输入参数,p是剩余过程。使用λ-抽象来对输入和绑定输出动作中的绑定效果进行建模,这意味着这些动作具有作为函数的意义,当使用名称实例化2一个没有底的域,其中每两个不可识别的元素都是不可比较的。3.| ⊥|} ±和在其他情况下是不可比较的。8B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3得到实际的残余物最后,约束的效果由定义在元素p∈P i上的新算子建模,如图3所示。new(x,n)=nnew(x,{|⊥|})={|⊥|}.new(x,{|in(y,λz.p)|})=如果x=y,{|in(y,λz. new(x,p))|},否则如果x=y,new(x,{|out(y,z,p)|})={|out(y,λz.p)|}, 如果x=z/= y⎪⎩{|out(y,z,ne w(x,p))|},否则,.new(x,{|out(y,λz.p)|})=如果x=y,{|out(y,λz. new(x,p))|},否则new(x,{|τ(p)|})={|tau(new(x,p))|}new(x,(p1p2))=new(x,p1)new(x,p2)图三. 新的定义。通常,new捕获由于尝试通过受限制的非挤出通道进行通信而引起的死锁情况。一旦通过通道直接发送受限制的消息,它还将自由输出转换为绑定输出(作用域挤出)。在所有其他情况下,限制没有效果,它只是简单地传递给剩余或分布在多集并上。使用元素p∈Pi,可以用语义函数S([(θ,P)])ρ φSδS∈P i来表示半π中系统的意义,该语义函数由P的结构上的归纳法定义,如图4所示。由于θ保持不变在整个解释过程中,用哲学的要素来解释一个系统是足够的。此语义介绍了以下环境。• 多重集ρ包含所有与分析过程并行组成的过程,并与θ的副本配对。标准的singleton,||}和多集并、、操作被重载以处理ρ的元素。• 特殊环境φS:N → N将一个名称映射到另一个名称,后者在语义中替代它。 初始时,<$n∈ N:φS0(n)= n。事实上,该环境将通过在通信期间接收的消息来保持输入参数的替换。由于标准指称语义是精确的语义,因此输入参数最多只能映射到任何可能的控制流选择中的一个名称(即,在任一侧)。• 特殊环境δS:Ω →A,它将半环变量映射为半环值。初始时,<$ω∈ Ω:δS0(ω)=<$,对于任意变量ω。ρ中的组合系统的含义由规则(R0)给出,B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)39(S1)S([(θ,0)])ρ φSδS=θ(S 2)S([(θ,x(y).P)])ρ φSδS={|in(φS(x),λy. R([{|(θ,P)|} ρ])φSδS)|}(S3)S([(θ,x<$y<$.P)])ρ φSδS=()在|τ(p)|)的文件 { 1}|输出(φS(x),φS(y),R([{|(θ,P)|} ρ])φSδS)|}(θ,x'(z).P')∈ρ其中,p = R([{|(θ,P)|} ρ [(θ,P ′)/(θ,x′(z).P ′)]])φS [z <$→ φS(y)] δSφS(x)=φS(x′).(S4)S([(θ,[x=y]P)])ρφSδS=(S5)S([(θ,[e1e2]P)])ρφSδS=.R([{|(θ,P)|} ρ])φSδS,如果φS(x)= φS(y)R([ρ])φSδS,否则R([{|(θ,P)|}ρ])φSδS,如果e1[δS(ω1)/ω1]ω1∈semiv(e1)e2[δS(ω2)/ω2]ω2∈semiv(e2)R([ρ])φSδS,否则(S 6)S([(θ,P |Q)])ρ φSδS= R([{|(θ,P)|}个字符。|(θ,Q)|} ρ])φSδS(S 7)S([(θ,(νx)P)])ρ φSδS= new(x,R([{|(θ,P)|} ρ])φSδS)(S 8)S([(θ,letω = Svalue(π,n)inP)])ρ φSδS= R([{|(θ,P)|} ρ])φSδS [ω<$→θ(π,n)].(S9)S([(θ,!P)])ρ φSδS=F其中,F ={{|⊥|}的情况下,R([{|(θ,P[bni(P)/bn(P)][semivi(P)/semiv(P)])|})ρ])φSδS}i=0. ∞并且,bni(P)={xi|x ∈ bn(P)},半i(P)={ωi|ω ∈ semiv(P)}(R 0)R([ρ])φSδS=S([(θ,P)])(ρ\{|(θ,P)|})φSδS(θ,P)∈ρ见图4。 半π的标准语义。每个系统的个别意义的总和 规则(S1)将空进程的含义直接解释为空的多重集.规则(S2)和(S3)处理由输入和输出动作保护的过程的情况,在此之后剩余由ρ的元素组成。匹配的输入/输出动作之间的任何通信都在规则(S3)中处理,其中φS相应地更新。 解释是所有这些COM的总和-通信和无通信的情况。 这保留了并行复合运算符P的结合性属性|Q. 规则(S4)根据两个名称的φS值的匹配来解释连接语句规则(S5)在δS环境下对两个表达式进行排序后,规则(S6)是直接的,允许两个并行进程与ρ中的其余进程组合,其中θ分布在两个进程上。规则(S7)使用new操作解释约束,如前面图3中所定义。在规则(S8)中,半环检索的意义是通过用一个动作π的半环值来更新δS,给定一个名字n。最后,规则(S9)定义了最小不10B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3动点B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)311复制过程的含义,!P作为偏序集F的最小上界,F包含底元素{|⊥|},以及表示复制过程P的任何数量(直到无穷大)的并行组成的元素。由于语义域Pi是无限的,F可以包含无限数量的元素,因此,它的最小上限可能在有限范围内不可计算。在规则中还使用了一种标记机制,通过下标P的所有绑定名称和半环变量来对产生的副本P执行α转换。重命名是必要的,以保持正常的过程。5非标准语义我们的主要兴趣是捕获输入参数和半环变量的实例化由于上一节的标准语义不提供这些信息,我们需要扩展它。为此,我们引入了两个特殊的环境φE:N→N(N)和δE:Ω→N(A),它们分别把一个名字映射到一个名字集合,把一个半环变量映射到一个半环值集合 这两个映射都表示可能的实例化,可以在运行时发生。 首先,我们有<$n∈ N:φE0(n)={n}和<$ω∈ Ω:δE0(ω)={}。由于没有束缚名和半环变量的同胚出现(定义3.1),那么对于任何名y和半环变量ω,集合φE(y)和δS(ω)将至多是每个控制流选择的单例。使用这些环境,我们可以定义非标准语义域,D=Pi×(N→N(N))×(Ω→A(A)),顺序如下:<$(p1,φE1,δE1),(p2,φE2,δE2)∈D<$:(p1,φE1,δE1)±D(p2,φE2,δE2) ⇔p1±p2φE1φE2δE1δE2其中,bottomtomelement是D=({|⊥|},φE0,δE0)。我们将φE和δE的并集定义如下:(φE1<$φφE2)(x)=φE1(x)<$φE2(x)(δE1<$δE2)(ω)=δE1(ω)<$δE2(ω)现在,我们可以使用函数E([(θ,P)])ρ φEδE∈D定义半π的非标准语义,如图5所示。语义利用多集合ρ来保持与分析过程并行的所有过程,共享θ的相同副本。ρ的内容用规则(R0)来解释,它用来对标准元素p∈Pi的选择和运算<$φ、<$δ进行分组,对非标准元素φE和δE的选择进行分组。的其余的规则(E1)有几值得注意的几点。名称和半环值实例化,(φJ,δJ),E E12B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3EEEEEEEEE(E1)E([(θ,0)])ρ φEδE=(θ,φE,δE)(E 2)E([(θ,x(y).P)])ρ φEδE=({|in(x′,λy.p′)|},φE,δE)其中,(p′,φ′,δE′)= R([{|(θ,P)|} ρ])φEδE并且,φE(x)={x′}(E3)E([(θ,x<$y<$.P)])ρ φEδE=({|τ(p′)|)的文件{|out(x",y",p")|}的情况下,(θ,x'(z).P')∈ρ(φ′)φ,(δ′)φδ)φEφEδE(θ,x'(z).P')∈ρ(θ,x'(z).P')∈ρ其中,(p′,φ′,δ′)= R([{|(θ,P)|} ρ [(θ,P ′)/(θ,x′(z).P ′)]])φE[z <$→ {y}] δE,EE(p′′,φ′′,δ′′)= R([{|(θ,P)|}ρ])φEδEEEφE(x)=φE(x′)={x′′},φE(y)={y′′}⎧⎪⎨R([{|(θ,P)|}ρ])φEδE,如果φz∈φE(x),z′∈φE(y):(E4)E([(θ,[x=y]P)])ρφEδE=(E5)E([(θ,[e1e2]P)])ρφEδE=⎧⎪⎩R([ρ])φδ,otherwisez=z′⎪⎨R([{|(θ,P)|}ρ])φEδE,如果φe∈(folddYδE{e1}sem iv(e1)),⎪⎩R([ρ])φδ,otherwisee′∈(folddYδE{e2}semiv(e2)):ee′(E 6)E([(θ,P|Q)])ρ φEδE= R([{|(θ,P)|}{|(θ,Q)|} ρ])φEδE(E7)E([(θ,(νx)P)])ρ φEδE=(new(x,p′),φ′,δE′)其中,(p′,φ′,δE′)= R([{|(θ,P)|} ρ])φEδE(E 8)E([(θ,let ω = Svalue(π,n)in P)])ρ φEδE= R([{|(θ,P)|}ρ])φEδE[ω <$→ {θ(π,n)}].(E9)E([(θ,!P)])ρ φEδE=F其中,F ={({|⊥|},φE0,δE0),R([{|(θ,P [bni(P)/bn(P)][semiv i(P)/semiv(P)])|)的文件ρ])φEδE}i=0. ∞并且,bni(P)={xi|x ∈ bn(P)},半i(P)={ωi|ω ∈ semiv(P)}(R0)R([ρ])φ δ=(p′,φ′,δ′)E E(θ,P)∈ρφ(θ,P)∈ρEδE(θ,P)∈ρ其中,(p′,φ′,δ′)= E([(θ,P)])(ρ\{|(θ,P)|})φEδE图五. 半π的非标准语义。在规则(E2)中,输入动作的剩余部分被忽略。在匹配输入和输出动作之B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)313间的通信期间,在规则(E3)中考虑这种实例化在这条规则中,类似的实例,(φJJ,δJJ),也被忽略。E E在规则(E4)中,匹配过程根据是否存在φE-匹配名称的相等或不相等的值。由于语义是精确的,这些值只能是每个控制流选择的单例集。14B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3在规则(E5)中也有类似的论证,其中任一表达式在δE下闭合时只能假定一个值。因此,半环约束要么满足,要么不满足。在这个规则中,我们定义了以下操作:foldfe{x1,.,xn}= f(xn,.,f(x1,e). . )应用函数YδE,其结构可在一组六个过程中变化以生成一组新的子表达式,如下所示:YδE(ω,{e1, .. . ,en})=({e1[s/ω]}). 1999年,{en[s/ω]})s∈ δE( ω)s∈δE(ω)复制规则(E9)将复制过程的最小不动点定义为(可能无限)偏序集F的最小上界。这个最小固定点的计算可能不会在有限限制内终止,因为D的大小是无限的。此外,任何衍生的副本!P是利用上一节介绍的标记机制进行α-转化的以维持过程正常性要求。下面的定理指出,半π的非标准语义是正确的标准语义。定理5.1(非标准语义的φP,θ,ρ,φS,φE,δS,δE:(S([(θ,P)])ρ φSδS=p) ∧ (E([(θ,P)])ρ φEδE=(pJ,φJ,δJ))p=pJE E直觉上,该定理指出,对于任何系统(θ,P),可以从其非标准意义E([(θ,P)])ρφEδE中提取其标准意义S([(θ,P)])ρ φ SδS。换句话说,前者等于后者生成的三元组的第一个元素。6抽象语义正如我们在前一节中提到的,semi-π的非标准语义包含最小不动点计算,由于具体语义域的无限性质,这些计算可能是不可因此,在本节中,我们将介绍几个抽象,它们有助于将语义域的大小限制在有限级别。首先,我们需要引入抽象半环、抽象表达式、β和的定义。定义6.1抽象半环(A,+,×,1,0)是这样的半环:|一|∞<.定义6.2一个抽象半环表达式e是从一个标准表达式e中得到的,通过将每次出现的s,+,×,1和0替换为它们的B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)315抽象形式,分别为s、+、×、1和0,并保持ω在e.定义6.3定义了抽象β:A → A,返回一个抽象半环值β(s)=s,对应于具体值s。我们在这里省略了β的定义,因为这取决于应用。6.4定义ssJ为s+sJ=s。我们可以写s>SJ来表示SJ和sj=SJ。接下来,我们引入一个有限的标签前域Tag,其范围为t,tJ等。给定一个过程P,我们将不同的标签放置在P的输出动作的所有消息上,除了那些在让ω=Svalue(π)inn中作为π出现的消息。 例如,标记-ging!(vx)yx。你好。y(z)。你要进去了!(vx)yxt。我也是。y(z)。yztJj. Copies可以通过在它们的下标上加上它们的副本编号来重命名因此,上面的复制在产生两个副本时变为:!(vx)yxt。我也是。y(z)。y⟨ztJJ⟩|t1tJtJJt2tJtJJ(v x1)yx .y|(v x2)yx .y1 1 2 2我们还定义了以下两个函数:• 的值({t1,.,tn})={x1,. .比如说,({t,t1,t2,tJ,tj,tJ,tjj,tJJ,tJJ})的值= { x,x 1,x 2,y,z,z1,z 2 }12 1 2• 标签(P)={t1,.,tn},当应用于进程P时,它返回P中的标记集。比如说,tagsof(!(vx)yxt。我也是。y(z)。y<$ztJ<$)={t,tJ,tJJ}现在,我们为名称、标记和半环变量定义,该函数对分析期间可以捕获的名称、标记和半环变量的副本总数设置上限k一般来说,选择k是不可判定的,并且在很大程度上依赖于用户定义6.5定义抽象函数αk:N×(N+T ag+ Ω)→(N+T ag+ Ω),如下:⎧zk,如果z=ziz∈(N+T ag+ Ω):αk(z)=否则,16B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3⊥D⊥⊥注意,N= N\{xj|j> k},Tag= Tag\{tj|j> k}且Ω = Ω\{ωj|j> k}。使用αk抽象函数和抽象半环(A,+,×,1, 0),我们可以定义抽象环境φA:N→δA:Ω→Ω(A)。由于摘要的不精确性在语义上,φA(x)和δA(ω)都可以大于单例集。 这个IM-精度的原因是无法区分输入参数、标签和第k个副本以外的半环变量的不同副本,以及使用抽象半环(A,+,×,1, 0)。抽象语义域D =(N→N(Tag))×(ω→N(A)),基于子集包含的排序如下(其中,φφ,φδ的定义与上一节相同,但在抽象环境而不是具体环境中):F(φA1,δA1),(φA2,δA2)∈D:(φA1,δA1)±(φA2,δA2)⊥D⊥φ A 1φ A 2 δA1底部的元素是对(φA0,δA0),映射每个抽象⊥name为空集,每个抽象半环变量为空分别设置。使用D,半π的抽象语义由函数A([(θ,P)])ρ φAδA∈D定义,如图6所示。多集ρ像往常一样包含所有与之并行的过程,解释过程,以及θ的副本。抽象语义的规则被非正式地描述如下。零过程和输入动作的规则(A1)和(A2)不会改变φA和δA的值,因为在这些规则中没有通信发生。 在规则(A3)中,输出动作由无通信和具有ρ中的匹配输入动作的通信这两种情况组成。只要两个通道的值的集合(由φA给出)具有非空交集,就触发通信通过将输出消息的标记添加到输入参数的φA值来在规则(A4)中,两个名字的匹配导致选择过程P或不选择过程P,这取决于每个匹配的名字至少有一个φA-值。在规则(A5)中,当求解半环约束时,也有类似的论证褶皱的定义与前一节类似,但我们将YδA重新定义为:Yδ (ω,{e,.,e})=({e[s/ω]}) 我...1999年,{e[s/ω]})将1n1s∈ δA( ω)ns∈ δA( ω)在规则(A8)中,我们使用抽象β将θ(π,n)返回的具体半环值抽象为抽象集合A的元素。的规则B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)317A A一一A A⊥D(A1)A([(θ,0)])ρ φAδA=(φA,δA)(A2)A([(θ,x(y).P)])ρ φAδA=(φA,δA)(A3)A([(θ,x<$yt<$.P)])ρ φ δ=(φ′)(δ′) δ)A AφA(θ,x'(z).P')∈ρφAδAδ一(θ,x'(z).P')∈ρ其中,(φ′,δ′)= R([{|(θ,P)|}ρ [(θ,P ′)/(θ,x′(z).P ′)]])φA [z<$→ φA(z)<${t}] δAA A并且,<$t ∈φA(x),t′∈φA(x′):(t)的值=(t′的值)(A4)A([(θ,[x=y]P)])ρ φAδA=.R([{|(θ,P)|} ρ])φAδA,如果φt ∈ φA(x),t′∈ φA(y):value of(t)= value of(t′)R([ρ])φAδA,否则( A5) A([(θ,[e1e2]P)])ρφAδA=⎧R([{|(θ,P)|}ρ])φAδA,如果φe∈(foldYδ{e}semiv(e)),A1 1e′∈(foldYδ{e}semiv(e)):ee′⎪⎩R([ρ])φδ,otherwiseA2 2(A 6)A([(θ,P|Q)])ρ φAδA=R([{|(θ,P)|}个字符。|(θ,Q)|} ρ])φAδA(A7)A([(θ,(νx)P)])ρ φAδA=R([{|(θ,P)|} ρ])φAδA(A8)A([(θ,令ω=P中的S值(π,n))])ρ φAδA=R([{|(θ,P)|} ρ])φAδA[ω<$→δA(ω) <${β(θ(π,n))}].(A9)A([(θ,!P)])ρ φAδA=F其中F={(φA0,δA0),R([{|(θ,ren(P,i,αk))|}ρ])φAδA}i=0. ∞并且,<$x∈bn(P),t∈(P)的标签,ω∈semiv(P):ren(P,i,αk)=P[αk(xi)/x][αk(ti)/t][αk(ωi)/ω](R0)R([ρ])φAδA=(φφ′,δ′)(θ,P)∈ρ(θ,P)∈ρ其中,(φ′,δ′)= A([(θ,P)])(ρ\{|(θ,P)|})φAδA见图6。 半π的抽象语义。复制进程(A9)根据每个进程的拷贝数,将抽象下标附加到派生进程的绑定名称、标记这将仅保持直到第k个副本的区分要求,因为在此之后,副本将被识别。因此,这种语义一定是近似的,D必然是有限的。该规则还定义了复制的最小不动点的含义为包含底元素F的偏序集F的最小上界。以来δ18B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3⊥⊥语义域D本质上是有限的,F只能包含有限个φA,δA元素。因此,最小固定点的计算保证终止。这一点更正式地表述如下。定理6.6(最小不动点计算的终止)B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)319⊥D规则(A9)的计算终止.证明草图:我们给出了一个草图的终止性的证明。必须满足两个要求。首先,语义域必须是没问题。 这是由D而事实上,名称,标签和emiring值仍然有限。第二个要求证明R([{|(θ,ren(P,i,αk))|}])φAδA±我的R({|(θ,ren(P,i +一期+11,αk))|}])φAδA(即,证明意义是单调的,(θ,P)的拷贝数的增量 为了证明这一点,我们将不等式简化为R([E])φAδA±R([E{|(θ,ren(P,i+1,αk))|}])φAδA,其中E={|(θ,ren(P,i,αk))|}。 这一结果可以通过对我规则A。 特别是,最有趣的规则是(A3)和(A8),其中φA和δA的值发生变化。该证明依赖于这样的事实,即在R([E])φAδA中发生的任何通信和半环值检索必然在R([E{|(θ,ren(P,i,αk))|}])φAδA,因为后者是一个比前者更大的系统,而更大的系统总是至少与较小的系统一样多地引入通信和半环值检索抽象语义的安全性现在可以在以下定理。定理6.7(半π的抽象语义的安全性)φθ,P,ρ,φE,φA,δE,δA,x,ω,αk,β,E([(θ,P)])ρ φEδE=(p,φJ,δJ),A([(θ,P)])ρ φAδA=(φJ,δJ):E E A A(n∈φE(x)) <$t∈φA(αk(x)):({t})= αk(y)的值<$(εs∈δE(ω)) ⇒ εs∈δA(αk(ω)):s= β(s))⇒(n∈φJ(x)) <$t∈φJ(αk(x)):({t})= αk(y)的值<$E A(ωs∈δJ(ω)) ⇒ εs∈δJ(αk(ω)):s= β(s))E A上面的安全性定理指出,存在于由具体非标准语义产生的最终环境中的值将始终作为抽象半环的抽象标记和元素存在于由抽象语义产生的环境中。7半环约束事实上,半环约束允许我们定义一个约束满足问题(CSP)[10,§2.1.1],如下所示:C =({ω1,...,ωn},{A1,.,An},{e1e2,.,ekek+1})20B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3一一一k+1其中reωi= 1.. . n∈半v(ej)。本文通过讨论,得到了问题的解答。j=1ing“good”instantiationsofthesemiringvariables,ω1. ωn,即满足约束集合{e1e2,.,ekek+1}。因此,一个解被定义为一个集合,Sol(C)={ω1<$→s1∈ A1,.,ωn<$→sn∈An}.此外,我们将所有解的集合称为SOL(C)={Sol1(C),. ,Solm(C)}。从集合SOL(C)中,可以如下将解决方案与名称替换的属性相关联假设C是一个上下文,即这是一个过程有一个洞,P。].这允许我们用一串半环约束写一个过程, 如C[[e1e2]. .[ekek+1]P]。然后,我们有以下两个环境:φA1=fst(A([(θ,C[P])])ρ φAδA)φA2=fst(A([(θ,C[0])])ρ φAδA)Whichesultfrom romrep la cing g[e1e2]... [ekek+1]PoncebyPandonceby0. 现在,我们将两种环境之间的差异定义如下:P=φA1\φA2φP环境表示在名称替换中所反映的效果,满足约束集合,{e1e2,.,ekek+1}。下面的定义形式化了名称替换/CSP依赖。定义7.1Givenasystemtem,(θ,C[[e1e2].. . [ekek+1]P]),anabs道在解释中,A([(θ,C[[e1e2]. . [ekek+1]P]))])ρφAδA=(φJ,δJ),以及A A一个差分环境,φP,那么每个替换,[x] → {a,...,a}] ∈将1nφP取决于达到一个或多个解SOL(C),使得:C=k+1J({ω|ω {set},{set}|set = δA(ω)},{e1j=1e2,. ,ekek+1})该属性声明名称替换只能在CSP满足抽象约束的情况下发生由于我们只处理正规过程,没有出现同伦半环变量或绑定名,所以可以通过观察一个子过程,让ω=P中的S值(π,z),在分析过程的语法中,将每个ω与某个抽象作用π和名称z这将允许我们在某些情况下将名称替换与行动成本联系起来φB. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)321我不8示例:自适应路由器在本节中,我们考虑一个简化的自适应路由器的例子。该系统主要由一个进程Router组成,它通过通道outi(i = 1.)连接到n个其他路由器。n.路由器重复接受一条消息(目的地),然后它查询状态θ,在每个输出连接上路由消息的开销。人们可能会认为θ是实现一些计算最短路径的算法,例如Dijkstra使用这些成本,路由器决定哪个连接是最好的发送消息。系统的规格如图7所示,其中它运行五个连接的路由器进程。def路由器(n)- - route(dest).设ω1=S值(出1dest,dest),.设ωn=S值(outn,dest,dest)in设ω1+n=S值(out1(x1),dest)in.设ωn+n=S值(outn(xn),dest)inni=1max({1,. . (i)([(ωi×ωn+i)(ωj×ωn+j)])utidesttj = min({1,. . (i)系统定义=(θ,路由器(5)| 路线终点 ⟩|5i(xi)i=1见图7。 路由协议的规范。在这里,我们使用特殊符号,K(i=1[eieJ])Pas a shortstand速记for,[e1eJ].. . [ekeJ]P1K我们首先采用以下假设来开始对该系统的分析• 这类环是一个新的半环,(R+,min,+,+∞,0).• θ包含不同动作的值,如下所示:θ(out1ourmsg,our dest,our dest)= 30θ(out2ourmsg,ourdest,our dest)= 322B. Aziz/Electronic Notes in Theoretical Computer Science 157(2006)3A我,δA我A我=φ一个2A我A我θ(out3)= 3,我们的消息,我们的目标,我们的目标θ(out4ourmsg,ourdest,our dest)= 1010θ(out5ourmsg,ourdest,our dest)= 60θ(out1(x1,y1),our dest)= 100θ(out2(x2,y2),our dest)= 5θ(out3(x3,y3),ourdest)= 10000θ(out4(x4,y4),our dest)= 50000θ(out5(x5,y5)
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 单片机串口通信仿真与代码实现详解
- LVGL GUI-Guider工具:设计并仿真LVGL界面
- Unity3D魔幻风格游戏UI界面与按钮图标素材详解
- MFC VC++实现串口温度数据显示源代码分析
- JEE培训项目:jee-todolist深度解析
- 74LS138译码器在单片机应用中的实现方法
- Android平台的动物象棋游戏应用开发
- C++系统测试项目:毕业设计与课程实践指南
- WZYAVPlayer:一个适用于iOS的视频播放控件
- ASP实现校园学生信息在线管理系统设计与实践
- 使用node-webkit和AngularJS打造跨平台桌面应用
- C#实现递归绘制圆形的探索
- C++语言项目开发:烟花效果动画实现
- 高效子网掩码计算器:网络工具中的必备应用
- 用Django构建个人博客网站的学习之旅
- SpringBoot微服务搭建与Spring Cloud实践
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功